Simple Polygon solution kickstart

Simple Polygon solution kickstart

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, TTTT 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 #xxyy, 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 0Xi,Yi1090≤Xi,Yi≤109 constraints. Vertices of the polygon should be listed in consecutive order ( vertexivertexi should be adjacent to vertexi1vertexi−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.
1T1001≤T≤100.
1A1091≤A≤109.

Test Set 1

Time limit: 20 seconds.
3N53≤N≤5.

Test Set 2

Simple Polygon solution kickstart

Time limit: 40 seconds.
3N10003≤N≤1000.

Sample

Simple Polygon solution kickstart

Sample Input
content_copy
2
4 36
5 2
Sample Output

Simple Polygon solution kickstart

content_copy
Case #1: POSSIBLE
2 5
6 5
8 2
0 2
Case #2: IMPOSSIBLE

diagram for sample case 1

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.

Leave a Comment