#216125. [COI 2018] Pick 皮克

1s，1024MB。

Mirko 最近读到了 皮克定理（Pick’s theorem），它的内容如下：在坐标系中，如果我们画一个顶点坐标都是整数的多边形，设其面积为 ，多边形内部的整数坐标点数量为 ，位于多边形边界上的整数坐标点数量（包括顶点）为 ，那么总是有：

为了验证这个定理，Mirko 使用他的智能白板，用磁性棒制作了一个多边形。由于重力作用，夜间棒子可能已经滑落到了白板底部。现在，Mirko 想在使用所有找到的棒子的情况下，构建面积最小的多边形。Mirko 可以在白板上移动棒子，但不得旋转它们。他拥有如下棒子：

• 根长度为 1 的水平棒，
• 根长度为 1 的垂直棒，
• 根长度为 的对角线棒，与 轴正方向形成 的夹角，
• 根长度为 的对角线棒，与 轴正方向形成 的夹角。

图 2：上述多边形：, , 。

图 3：Mirko 所拥有的棒子。

请确定可以构建的最小面积多边形，使得所有棒子都被使用。可以假设输入数据保证至少能构建一个多边形。

如果你使用所有给定棒子构建了一个有效多边形（不一定是最小面积的），也可以获得部分分数。更多细节请参见“评分”部分。

第一行输入四个整数，分别是题目中提到的 。

输出 行，其中 。第 行输出整数 和 ——第 个多边形顶点的坐标。第一个顶点必须是 ，其他顶点可以按任意方向打印（正方向或负方向）。允许连续多边形边平行，但多边形不能自相交或自接触。

样例输入 1

1 1 1 0

样例输出 1

0 0
1 1
0 1

样例输入 2

0 0 6 4

样例输出 2

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

数据范围

在所有子任务中，有 且 。

子任务

::cute-table{three} |编号 |分值 |限制条件 | |:--:|:--:|:--------:| | | || | | || | ||| | ||| | ||| | ||| | ||| | ||| | ||| |||无额外限制 |

评分

如果在某个测试用例中，你的解没有输出一个有效的多边形，则该子任务得 分。如果输出的多边形有效，但不是最小面积，多边形仍可获得部分分数：

对于测试用例 ，记 为输出多边形面积与最小可能面积的比值。对于子任务 ，记 为子任务 中所有 的最大值。得分百分比 计算如下：如果 ，则 ，否则：

因此，非最优解在某个子任务中可获得 至 的分数，具体取决于多边形面积比。

翻译来源：GPT 4.1 mini。