Table of Contents

# Simple Polygon solution kickstart Round G

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.

### Input Simple Polygon solution kickstart

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

Time limit: 40 seconds.

3≤N≤10003≤N≤1000.

### Sample Simple Polygon solution kickstart

2 4 36 5 2

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

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.