SRM 585 1 1000 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

Limits

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.

Test cases

0. input

   • m 4
   • x { 1, 2, 3 }
   • y { 1, 3, 2 }

   output

   Returns 19

   note

   The picture shows the 19 ways to draw a triangle.
   
   
1. input

   • m 7
   • x { 1, 1, 6, 6 }
   • y { 1, 6, 1, 6 }

   output

   Returns 0
2. input

   • m 4
   • x { 2 }
   • y { 2 }

   output

   Returns 224
3. input

   • m 10
   • x { 2, 6, 7, 6 }
   • y { 7, 7, 9, 3 }

   output

   Returns 81
4. input

   • m 15
   • x { 7, 6, 5, 4, 3 }
   • y { 1, 4, 7, 10, 13 }

   output

   Returns 283