题目背景

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)$，其他顶点可以按任意方向打印（正方向或负方向）。允许连续多边形边平行，但多边形不能自相交或自接触。

1 1 1 0

0 0
1 1
0 1

0 0 6 4

0 0
1 1
2 2
3 3
2 4
1 3
0 2
-1 3
-2 2
-1 1

提示

数据范围

在所有子任务中，有 $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。