EnclosingTriangle

Problem Statement

You are given an int m. Consider a square in the plane such that the corners of the square have coordinates (0, 0), (m, 0), (m, m), and (0, m). All the lattice points on the boundary of this square are red. That is, the red points have coordinates (0, 0), (1, 0), ..., (m, 0), (m, 1), ..., (m, m), (m-1, m), ..., (0, m), (0, m-1), ..., and (0, 1).

Some other lattice points are black. Each black point lies strictly inside the square. You are given two int[]s: x and y. These describe the black points: For each i, there is a black point at (x[i], y[i]).



You want to draw a triangle such that:

1. all three of its vertices are red,
2. all black points lie inside or on the boundary of the triangle.

Return the number of ways to draw such a triangle.

Definition

Class:

EnclosingTriangle

Method:

getNumber

Parameters:

int, int[], int[]

Returns:

long

Method signature:

long getNumber(int m, int[] x, int[] y)

(be sure your method is public)

Constraints

• m will be between 2 and 58,585, inclusive.
• x and y will each contain between 1 and 20 elements, inclusive.
• x and y will contain the same number of elements.
• Each element of x and y will be between 1 and m-1, inclusive.
• All points described by x and y will be distinct.

Examples

1. 4

   { 1, 2, 3 }

   { 1, 3, 2 }

   Returns: 19

   The picture shows the 19 ways to draw a triangle.

2. 7

   { 1, 1, 6, 6 }

   { 1, 6, 1, 6 }

   Returns: 0

3. 4

   { 2 }

   { 2 }

   Returns: 224

4. 10

   { 2, 6, 7, 6 }

   { 7, 7, 9, 3 }

   Returns: 81

5. 15

   { 7, 6, 5, 4, 3 }

   { 1, 4, 7, 10, 13 }

   Returns: 283