给你一张简单多边形 $$$S$$$ 形状的纸。你的任务是把它变成一个简单的多边形$$$T$$$,其面积与$$$S$$$相同。
您可以使用两种工具:剪刀和胶带。剪刀可用于将任何多边形切割成更小的多边形块。胶带可用于将较小的碎片组合成较大的多边形。您可以按任何顺序多次使用每个工具。
输入中给出的多边形具有整数坐标,但您可以在输出中生成具有非整数坐标的形状。
任务的正式定义如下。
形状 $$$Q=(Q_0,\dots,Q_{n-1})$$$ 是平面上三个或更多点的序列,使得:
- 闭合折线 $$$Q_0Q_1Q_2\dots Q_{n-1}Q_0$$$ 永远不会接触或相交自身,因此它形成简单多边形的边界。
- 多段线以逆时针方向围绕多边形的边界。
边界为 $$$Q$$$ 形状的多边形将表示为 $$$P(Q)$$$。
如果两个形状可以平移和/或旋转以变得与另一个相同,则称为等效。
请注意,不允许镜像形状。另请注意,点的顺序很重要:形状 $$$(Q_1,\dots,Q_{n-1},Q_0)$$$ 不一定等于形状 $$$(Q_0,\dots,Q_{n-1})$$$。
在左图中:形状 $$$U$$$ 和 $$$V$$$ 是等效的。形状 $$$W$$$ 与它们不等价,因为 $$$W$$$ 的点以不同的顺序给出。无论点的顺序如何,第四个形状都不与前面的形状等效,因为不允许翻转形状。
在输入和输出中,具有 $$$n$$$ 点的形状表示为包含 $$$2n+1$$$ 空格分隔数字的单行:数字 $$$n$$$ 后跟点的坐标:$$$Q_{0,x}$$$, $$$Q_{0,y}$$$, $$$Q_{1,x}$$$, ...
形状具有标识号 (ID)。给定形状 $$$S$$$ 的 ID 为 0,您在解决方案中生成的形状的 ID 为 1、2、3、...,按照生成的顺序排列。
形状 $$$B_1,\dots,B_k$$$ 形成形状 $$$A$$$ 的细分,如果:
- 所有 $$$P(B_i)$$$ 的并集恰好是 $$$P(A)$$$。
- 对于每个 $$$i\neq j$$$,$$$P(B_i)$$$ 和 $$$P(B_j)$$$ 的交集面积为零。
剪刀操作会破坏一个现有形状 $$$A$$$ 并生成一个或多个形状 $$$B_1,\dots,B_k$$$,形成 $$$A$$$ 的细分。
图中:形状$$$A$$$(正方形)细分为形状$$$B_1$$$、$$$B_2$$$、$$$B_3$$$(三个三角形)。描述 $$$B_i$$$ 之一的有效方法是“3 3 1 6 1 5.1 4”。
磁带操作会破坏一个或多个现有形状 $$$A_1,\dots,A_k$$$ 并生成一个新形状 $$$B$$$。为了执行此操作,您必须首先指定形状 $$$C_1,\dots,C_k$$$,然后才是最终形状 $$$B$$$。这些形状必须满足以下条件:
- 对于每个 $$$i$$$,形状 $$$C_i$$$ 相当于形状 $$$A_i$$$。
- 形状 $$$C_1,\dots,C_k$$$ 形成形状 $$$B$$$ 的细分。
非正式地,您选择形状 $$$B$$$ 并展示如何将每个现有 $$$A_i$$$ 移动到 $$$B$$$ 内的正确位置 $$$C_i$$$。请注意,只有形状 $$$B$$$ 获得新 ID,形状 $$$C_i$$$ 则没有。
输入
第一行包含源形状 $$$S$$$。
第二行包含目标形状$$$T$$$。
每个形状都有 3 到 10 个点(含)。两种形状均按上述指定的格式给出。
输入中的所有坐标均为 $$$-10^6$$$ 和 $$$10^6$$$(含)之间的整数。
在每个形状中,没有三个点形成的角度小于 3 度。 (这包括不连续的点,并且意味着没有三个点共线。)
多边形 $$$P(S)$$$ 和 $$$P(T)$$$ 具有相同的面积。
输出
每当您使用剪刀操作时,都会输出以下形式的行块:
其中 $$$id(A)$$$ 是要销毁的形状的 ID,$$$k$$$ 是要生成的新形状的数量,$$$B_1,\dots,B_k$$$ 是这些形状。
每当您使用磁带操作时,都会输出以下形式的行块:
其中 $$$k$$$ 是要粘贴在一起的形状数量,$$$id(A_1),\dots,id(A_k)$$$ 是它们的 ID,$$$C_1,\dots,C_k$$$ 是显示它们在 $$$B$$$ 中位置的等效形状,$$$B$$$ 是将它们粘贴在一起获得的最终形状。
建议输出点的坐标至少为 10 位小数。
输出必须满足以下条件:
- 输出中点的所有坐标必须在 $$$-10^7$$$ 和 $$$10^7$$$ 之间(含边界值)。
- 输出中的每个形状最多必须有 $$$100$$$ 点。
- 在每个操作中,形状的数量 $$$k$$$ 必须介于 $$$1$$$ 和 $$$100$$$ 之间(含边界值)。
- 操作次数不得超过 $$$2000$$$。
- 输出中所有形状的点数总数不得超过 $$$20000$$$。
- 最后,必须有一个形状(尚未被破坏),并且该形状必须等于$$$T$$$。
- 根据检查器,所有操作必须有效。具有较小舍入误差的解决方案将被接受。 (在内部,验证每个条件时,所有比较都会检查高达 $$$10^{-3}$$$ 的绝对或相对误差。)
示例
输入 #1
6 0 0 6 0 6 4 5 4 5 9 0 9 4 0 0 7 0 7 7 0 7
输出 #1
scissors 0 5 3 0 0 3 0 3 4 3 3 4 0 4 0 0 3 3 0 6 0 6 4 3 6 4 3 4 3 0 4 0 4 5 4 5 9 0 9 tape 5 1 2 5 3 4 3 0 3 0 0 4 0 3 4 0 7 0 7 4 4 0 3 4 0 7 4 3 7 3 7 4 7 7 3 7 3 3 7 0 7 0 3 4 0 0 7 0 7 7 0 7
输入 #2
4 0 0 3 0 3 3 0 3 4 7 -1 10 -1 11 2 8 2
输出 #2
scissors 0 2 3 0 0 1 3 0 3 4 1 3 0 0 3 0 3 3 tape 2 1 2 3 110 -1 111 2 110 2 4 108 2 107 -1 110 -1 110 2 4 107 -1 110 -1 111 2 108 2
输入 #3
4 0 0 9 0 9 1 0 1 4 0 0 3 0 3 3 0 3
输出 #3
scissors 0 2 4 1.470000000 0 9 0 9 1 1.470000000 1 4 0 0 1.470000000 0 1.470000000 1 0 1 scissors 1 2 4 1.470000000 0 6 0 6 1 1.470000000 1 4 9 0 9 1 6 1 6 0 tape 2 4 3 4 3 2 3 1 6 1 6 2 4 6 1 1.470000000 1 1.470000000 0 6 0 6 1.470000000 0 6 0 6 2 3 2 3 1 1.470000000 1 scissors 5 4 4 1.470000000 0 3 0 3 1 1.470000000 1 4 3 0 4 0 4 2 3 2 4 4 2 4 0 5 0 5 2 4 5 0 6 0 6 2 5 2 tape 5 2 6 7 8 9 4 0 0 1.470000000 0 1.470000000 1 0 1 4 1.470000000 0 3 0 3 1 1.470000000 1 4 0 2 0 1 2 1 2 2 4 0 2 2 2 2 3 0 3 4 3 3 2 3 2 1 3 1 4 0 0 3 0 3 3 0 3
注意
评分:
如果某个形状对于某些正整数 $$$x$$$ 和 $$$y$$$ 具有 $$$((0,0),~ (x,0),~ (x,y),~ (0,y))$$$ 的形式,则该形状被称为漂亮矩形。
如果另外$$$x=y$$$,则形状被称为漂亮的正方形。
如果多边形 $$$P(A)$$$ 的所有内角都小于 180 度,则形状 $$$A$$$ 被称为严格凸形。
子任务 1(5 分):$$$S$$$ 和 $$$T$$$ 是漂亮的矩形。所有点的所有坐标均为 0 到 10 之间的整数(含 0 和 10)
子任务2(13分):$$$S$$$是一个漂亮的矩形,$$$x>y$$$,$$$T$$$是一个漂亮的正方形
子任务 3(12 分):$$$S$$$ 和 $$$T$$$ 是漂亮的矩形
子任务 4(14 分):$$$S$$$ 是一个三角形,$$$T$$$ 是一个漂亮的正方形
子任务5(10分):$$$S$$$和$$$T$$$是三角形
子任务6(16分):$$$S$$$是一个严格的凸多边形,$$$T$$$是一个漂亮的矩形
子任务 7(11 分):$$$T$$$ 是一个漂亮的矩形
子任务8(19分):无额外限制
下图显示了第一个示例输出。左边是使用剪刀后的原始图,右边是我们将这些碎片重新粘在一起时对应的$$$C_i$$$。
在第二个示例输出中,请注意,如果最终形状等于目标形状就足够了,它们不必相同。
下图显示了第三个示例输出的三个阶段。首先,我们将输入矩形切成两个较小的矩形,然后将这两个矩形中较大的矩形切成另外两个。这些切割后的状态显示在图的左上部分。
继续,我们将两个新矩形粘在一起形成一个六边形,然后将该多边形切割成三个 2×1 矩形和一个较小的矩形。这显示在图的左下部分。
最后,我们使用第一步中仍然保留的矩形和四个新矩形,并将它们组装成所需的 3×3 正方形。