P16190 [COI 2018] Pick 皮克

1s，1024MB。

Mirko 最近读到了 *皮克定理（Pick’s theorem）*，它的内容如下：在坐标系中，如果我们画一个顶点坐标都是整数的多边形，设其面积为 $A$，多边形内部的整数坐标点数量为 $i$，位于多边形边界上的整数坐标点数量（包括顶点）为 $b$，那么总是有： $$A=i+\frac{b}{2}-1$$ 为了验证这个定理，Mirko 使用他的智能白板，用磁性棒制作了一个多边形。由于重力作用，夜间棒子可能已经滑落到了白板底部。现在，Mirko 想在使用所有找到的棒子的情况下，构建面积最小的多边形。Mirko 可以在白板上移动棒子，但不得旋转它们。他拥有如下棒子： - $a$ 根长度为 1 的水平棒， - $b$ 根长度为 1 的垂直棒， - $c$ 根长度为 $\sqrt{2}$ 的对角线棒，与 $x$ 轴正方向形成 $45\degree$ 的夹角， - $d$ 根长度为 $\sqrt{2}$ 的对角线棒，与 $x$ 轴正方向形成 $135\degree$ 的夹角。  图 2：上述多边形：$A = 8$, $i = 4$, $b = 10$。  图 3：Mirko 所拥有的棒子。 请确定可以构建的最小面积多边形，使得所有棒子都被使用。可以假设输入数据保证至少能构建一个多边形。 如果你使用所有给定棒子构建了一个有效多边形（不一定是最小面积的），也可以获得部分分数。更多细节请参见“评分”部分。

第一行输入四个整数，分别是题目中提到的 $a,b,c,d$。

输出 $n$ 行，其中 $n = a + b + c + d$。第 $j$ 行输出整数 $x_j$ 和 $y_j$——第 $j$ 个多边形顶点的坐标。第一个顶点必须是 $(0, 0)$，其他顶点可以按任意方向打印（正方向或负方向）。允许连续多边形边平行，但多边形不能自相交或自接触。

### 数据范围 在所有子任务中，有 $0 \le a, b, c, d \le 100$ 且 $a + b + c + d \ge 3$。 ### 子任务 ::cute-table{three} |编号 |分值 |限制条件 | |:--:|:--:|:--------:| |$1$ |$5$ |$c = d = 0$| |$2$ |$5$ |$a = b = 0$| |$3$ |$10$|$a + b + c + d \le 6$| |$4$ |$10$|$a + b + c + d \le 20$| |$5$ |$10$|$a + b + c + d \le 40$| |$6$ |$10$|$a + b + c + d \le 80$| |$7$ |$10$|$a + b + c + d \le 150$| |$8$ |$10$|$a + b + c + d \le 200$| |$9$ |$10$|$a + b + c + d \le 300$| |$10$|$20$|无额外限制 | ### 评分 如果在某个测试用例中，你的解没有输出一个有效的多边形，则该子任务得 $0$ 分。如果输出的多边形有效，但不是最小面积，多边形仍可获得部分分数： 对于测试用例 $j$，记 $r_j$ 为输出多边形面积与最小可能面积的比值。对于子任务 $k$，记 $z_k$ 为子任务 $k$ 中所有 $r_j$ 的最大值。得分百分比 $P_k$ 计算如下：如果 $z_k \ge 3$，则 $P_k = 10$，否则： $$P_k = \frac{25}{8}(3 - z_k)^4 + 10$$ 因此，非最优解在某个子任务中可获得 $10\%$ 至 $60\%$ 的分数，具体取决于多边形面积比。 翻译来源：GPT 4.1 mini。