EnclosingTriangle
SRM 585 · 2013-06-25 · by lyrically
SRM 585 · 2013-06-25 · by lyrically · Geometry
Problem Statement
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 twoint[] 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:
Some other lattice points are black. Each black point lies strictly inside the square. You are given two
You want to draw a triangle such that:
- all three of its vertices are red,
- all black points lie inside or on the boundary of the triangle.
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
0)
4
{ 1, 2, 3 }
{ 1, 3, 2 }
Returns: 19
The picture shows the 19 ways to draw a triangle.
1)
7
{ 1, 1, 6, 6 }
{ 1, 6, 1, 6 }
Returns: 0
2)
4
{ 2 }
{ 2 }
Returns: 224
3)
10
{ 2, 6, 7, 6 }
{ 7, 7, 9, 3 }
Returns: 81
4)
15
{ 7, 6, 5, 4, 3 }
{ 1, 4, 7, 10, 13 }
Returns: 283
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EnclosingTriangle with a public method long long getNumber(int m, vector<int> x, vector<int> y) · 56 test cases · 2 s / 256 MB per case