EnclosingTriangleColorful
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 sides of this square are colored, as described below:
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:
- The points with coordinates (1, 0), ..., (m-1, 0) are red.
- The points with coordinates (m, 1), ..., (m, m-1) are green.
- The points with coordinates (m-1, m), ..., (1, m) are blue.
- The points with coordinates (0, m-1), ..., (0, 1) are yellow.
You want to draw a triangle such that:
- its vertices have three distinct colors out of the set { red, green, blue, yellow },
- all black points lie inside or on the boundary of the triangle.
Constraints
- m will be between 2 and 300, inclusive.
- x and y will each contain between 1 and 50 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: 8
The picture shows the 8 ways to draw a triangle.
1)
7
{ 1, 1, 6, 6 }
{ 1, 6, 1, 6 }
Returns: 0
2)
4
{ 2 }
{ 2 }
Returns: 72
3)
10
{ 2, 6, 7, 6 }
{ 7, 7, 9, 3 }
Returns: 52
4)
15
{ 7, 6, 5, 4, 3 }
{ 1, 4, 7, 10, 13 }
Returns: 150
Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EnclosingTriangleColorful with a public method int getNumber(int m, vector<int> x, vector<int> y) · 64 test cases · 2 s / 256 MB per case