23264번 - Simple Polygon 서브태스크스페셜 저지다국어

문제

You are given two 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 two consecutive edges form a straight angle.

입력

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

출력

For each test case, output one 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 two 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 ≤ 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.

제한

• 1ドル \le T \le 100$.
• 1ドル \le A \le 10^9$.

Test Set 1 (15점)

시간 제한: 20 초

• 3ドル \le N\le 5$.

Test Set 2 (24점)

시간 제한: 40 초

• 3ドル \le N \le 1000$.

힌트