P16864 [GKS 2021 #G] Simple Polygon

You are given $2$ integers, the number of vertices $N$ and area $A$. You need to construct a simple polygon of $N$ vertices such that the area of the polygon is exactly $\frac{A}{2}$, and all the vertices have non-negative integer coordinates with value up to $10^9$. A simple polygon is one that: - Defines a closed area. - Does not have self-intersections, even at a single point. - No $2$ consecutive edges form a straight angle.

The $1$st line of the input gives the number of test cases, $T$. $T$ lines follow. The $1$st line of each test case contains $2$ integers, $N$ denoting the number of vertices and $A$, denoting double the required area of the polygon.

For each test case, output $1$ line containing Case # $x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is `IMPOSSIBLE` if it is not possible to construct a polygon with the given requirements and `POSSIBLE` otherwise. If you output `POSSIBLE`, output $N$ more lines with $2$ integers each. The $i$-th line should contain $2$ integers $X_i$ and $Y_i$ which denote the coordinates of the $i$-th vertex. For each $i$, the coordinates should satisfy the $0 \le X_i, Y_i \le 10^9$ constraints. Vertices of the polygon should be listed in consecutive order ($vertex_i$ should be adjacent to $vertex_{i-1}$ and $vertex_{i+1}$ in the polygon). If there are multiple possible solutions, you can output any of them.

In Sample Case #$1$, we can output the above quadrilateral with coordinates $(2, 5)$, $(6, 5)$, $(0, 2)$ and $(8, 2)$. The area of this quadrilateral is equal to $18$. In Sample Case #$2$, there is no way to construct a polygon with $5$ vertices and area equal to $1$. :::align{center}  ::: ### Limits $1 \le T \le 100$. $1 \le A \le 10^9$. **Test Set $1$** $3 \le N \le 5$. **Test Set $2$** $3 \le N \le 1000$.