P16864 [GKS 2021 #G] Simple Polygon
题目描述
给定两个整数：顶点数 $N$ 和面积 $A$。你需要构造一个具有 $N$ 个顶点的简单多边形，使得其面积恰好为 $\frac{A}{2}$，并且所有顶点均为非负整数坐标，坐标值不超过 $10^9$。
简单多边形满足：
- 定义了一个封闭区域。
- 没有自交，即使在一个点处也不相交。
- 没有两条相邻的边形成平角。
输入格式
输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。每个测试用例的第一行包含两个整数 $N$ 和 $A$，分别表示多边形的顶点数和所需多边形面积的两倍。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 `IMPOSSIBLE`（如果无法构造满足要求的多边形），否则为 `POSSIBLE`。
如果输出 `POSSIBLE`，则再输出 $N$ 行，每行包含两个整数。第 $i$ 行应包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个顶点的坐标。对于每个 $i$，坐标应满足 $0 \le X_i, Y_i \le 10^9$ 的限制。多边形的顶点应按连续顺序列出（在多边形中，$vertex_i$ 应与 $vertex_{i-1}$ 和 $vertex_{i+1}$ 相邻）。
如果存在多个可能的解，你可以输出其中任意一个。
说明/提示
在样例 #1 中，我们可以输出上述坐标为 $(2, 5)$、$(6, 5)$、$(0, 2)$ 和 $(8, 2)$ 的四边形。该四边形的面积为 $18$。
在样例 #2 中，无法构造具有 $5$ 个顶点且面积为 $1$ 的多边形。
:::align{center}
:::
### 限制条件
$1 \le T \le 100$。
$1 \le A \le 10^9$。
**测试集 1**
$3 \le N \le 5$。
**测试集 2**
$3 \le N \le 1000$。
翻译由 DeepSeek V4 Pro 完成