InsidePoints
TCO19 Round 4 · 2019-04-15 · by misof
TCO19 Round 4 · 2019-04-15 · by misof · Geometry, Greedy
Problem Statement
Problem Statement
You are given a set of grid points in the plane. Construct any reasonably small polygon P with vertices in other grid points such that the given points are precisely all the grid points that are strictly inside P.
More precisely:
- Your polygon must have between 3 and 300 vertices, inclusive.
- The polygon must be simple. (I.e., all vertices must be distinct and each pair of edges must be disjoint, with the exception that consecutive edges share one point. Having three consecutive vertices on a line is allowed.)
- All coordinates of its vertices must be in [-100,100].
- You must return a
int[] containing the coordinates of the vertices of your polygon, as follows: { P[0].x, P[0].y, P[1].x, P[1].y, ... }. You may print the points of P in either direction (clockwise or counter-clockwise).
If a polygon with the desired properties does not exist, return an empty
Constraints
- x will have between 0 and 30 elements, inclusive.
- y will have the same number of elements as x.
- Each element of x will be between 1 and 50, inclusive.
- Each element of y will be between 1 and 50, inclusive.
- The points described by x and y will be distinct.
Examples
0)
{4}
{7}
Returns: {3, 7, 4, 8, 5, 6 }
Many other polygons are possible.
1)
{4, 6}
{7, 7}
Returns: {3, 6, 7, 6, 7, 8, 5, 7, 3, 8 }
2)
{1, 1, 2, 2}
{1, 2, 1, 2}
Returns: {0, 0, 3, 0, 3, 3, 0, 3 }
3)
{1, 2, 3, 3, 3, 3, 5, 4}
{3, 3, 1, 5, 2, 4, 3, 3}
Returns: {0, 2, 2, 2, 2, 0, 4, 0, 4, 2, 6, 2, 6, 4, 4, 4, 4, 6, 2, 6, 2, 4, 3, 3, 1, 4, 0, 4 }
4)
{}
{}
Returns: {0, 0, 1, 0, 1, 1 }
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class InsidePoints with a public method vector<int> construct(vector<int> x, vector<int> y) · 109 test cases · 2 s / 256 MB per case