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 int[] instead.
Definition
- Class:
- InsidePoints
- Method:
- construct
- Parameters:
- int[], int[]
- Returns:
- int[]
- Method signature:
- int[] construct(int[] x, int[] y)
- (be sure your method is public)
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
{4}{7}Returns: {3, 7, 4, 8, 5, 6 }Many other polygons are possible.{4, 6}{7, 7}Returns: {3, 6, 7, 6, 7, 8, 5, 7, 3, 8 }{1, 1, 2, 2}{1, 2, 1, 2}Returns: {0, 0, 3, 0, 3, 3, 0, 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 }
Back to all problems