Simple Polygon solution kickstart
-
For Solution
Click Here!
Problem
You are given two integers, the number of vertices NN and area AA. You need to construct a simple polygon of NN vertices such that the area of the polygon is exactly A2A2, and all the vertices have non-negative integer coordinates with value up to 109109.
A simple polygon is one that:
- Defines a closed area.
- Does not have self-intersections, even at a single point.
- No two consecutive edges form a straight angle.
Simple Polygon solution kickstart
Input
The first line of the input gives the number of test cases, TT. TT lines follow. The first line of each test case contains two integers, NN denoting the number of vertices and AA, denoting double the required area of the polygon.
Output
Simple Polygon solution kickstart
For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is IMPOSSIBLE if it is not possible to construct a polygon with the given requirements and POSSIBLE otherwise.
If you output POSSIBLE, output NN more lines with 22 integers each. The ii-th line should contain two integers XiXi and YiYi which denote the coordinates of the ii-th vertex. For each ii, the coordinates should satisfy the 0≤Xi,Yi≤1090≤Xi,Yi≤109 constraints. Vertices of the polygon should be listed in consecutive order ( vertexivertexi should be adjacent to vertexi−1vertexi−1 and vertexi+1vertexi+1 in the polygon).
If there are multiple possible solutions, you can output any of them.
Limits
Simple Polygon solution kickstart
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤A≤1091≤A≤109.
Test Set 1
Time limit: 20 seconds.
3≤N≤53≤N≤5.
Test Set 2
Simple Polygon solution kickstart
Time limit: 40 seconds.
3≤N≤10003≤N≤1000.
Sample
Simple Polygon solution kickstart
2 4 36 5 2
Sample Output
Simple Polygon solution kickstart
Case #1: POSSIBLE 2 5 6 5 8 2 0 2 Case #2: IMPOSSIBLE
Simple Polygon solution kickstart
In Sample Case #1, we can output the above quadrilateral with coordinates (2,5)(2,5), (6,5)(6,5), (0,2)(0,2) and (8,2)(8,2). The area of this quadrilateral is equal to 1818.
In Sample Case #2, there is no way to construct a polygon with 55 vertices and area equal to 11.
-
For Solution
Click Here!