题目描述

译自 CEOI 2019 Day2 T3「Scissors and Tape」

给定一张简单多边形 $S$ 形状的纸。你的任务是把他变成和 $S$ 面积相同的简单多边形 $T$。

你可以使用两种工具：剪刀和胶带。剪刀可以把任何多边形剪成一些小多边形。胶带可以把小多边形组合成一个大多边形。你可以任意顺序使用两个工具任意次。

输入给定的多边形的顶点坐标均为整数，但是你的输出允许产生顶点坐标不是整数的多边形。

这个问题的形式化定义如下。

形状 $Q=(Q_0,\ldots ,Q_{n-1})$ 是一个平面上三个点及以上的点列，满足：

• 闭合折线 $Q_0Q_1Q_2\ldots Q_{n-1}Q_0$ 不会接触自身或与自身相交，因此这个边界是一个简单多边形；
• 这段折线以逆时针方向绕行多边形的边界。

若一个多边形的边界为形状 $Q$，则记这个多边形为 $P(Q)$。

两个形状等价当且仅当一个形状经过平移或旋转之后和另一个形状相同。

注意不允许做一个形状的对称，并且点的顺序与形状有关：形状 $(Q_1,\ldots , Q_{n-1},Q_0)$ 不一定等价于形状 $(Q_0,\ldots ,Q_{n-1})$。

在上图中，形状 $U$ 与 $V$ 是等价的。形状 $W$ 与它们不等价，因为形状 $W$ 的点顺序与二者不同。不考虑点的顺序的情况下，第四个形状与前三个都不等价，因为不允许翻转一个图形。

在输入和输出中，一个有着 $n$ 个点的形状用一行 $2n+1$ 个被空格分开的数表示：一个数 $n$，后面紧接着这 $n$ 个点的坐标：$Q_{0,x},Q_{0,y},Q_{1,x},\ldots$。

每个形状都有一个编号（IDs）。给定的形状 $S$ 的 ID 为 $0$。你在答案中产生的形状按产生顺序编号为 $1,2,3,\ldots$。

形状 $B_1,B_2,\ldots ,B_k$ 构成一个形状 $A$ 的划分，如果：

• 所有 $P(B_i)$ 组合在一起与 $P(A)$ 完全相同；
• 对于任意 $i,j$，$i\neq j$，$P(B_i)$ 与 $P(B_j)$ 不相交。

剪刀可以剪开一个存在的形状 $A$，并且产生一个及以上的形状 $B_1,\ldots ,B_k$，这些形状构成形状 $A$ 的一个划分。

例如上图：形状 $A$（一个正方形）被划分为形状 $B_1,B_2,B_3$（三个三角形）。对于 $B_i$，一个合法的描述为：$3~3~1\ 6 \ 1\ 1\ 5.1\ 4$。

胶带可以粘合存在的形状 $A_1,\ldots ,A_k$，并构成一个新形状 $B$。为了实现这个操作，你需要先指定形状 $C_1,\ldots ,C_k$，然后才能得到形状 $B$。这些形状必须满足以下条件：

• 对于每个 $i$，形状 $C_i$ 与 $A_i$ 等价；
• 形状 $C_1,\ldots ,C_k$ 是形状 $B$ 的一个划分。

通俗地说，你选择了形状 $B$，然后展示如何把每个存在的 $A_i$ 移动到构成 $B$ 的正确的位置 $C_i$。注意形状 $B$ 需要分配一个新 ID，但 $C_i$ 不需要。

输入格式

第一行包含原来的形状 $S$；

第二行包含目标形状 $T$。

每个形状按照题目描述中的格式给出。

输出格式

每当使用剪刀时，按以下格式输出一些行：

scissors
id(A) k
B_1
B_2
...
B_k

其中，$\texttt{id}(A)$ 是你想要剪掉的形状 $A$ 的 ID。$k$ 是你想要产生的新形状个数，$B_1,\ldots ,B_k$ 是产生的新形状。

每当使用剪刀时，按以下格式输出一些行：

tape
k id(A_1) ... id(A_k)
C_1
C_2
...
C_k
B

其中，$k$ 表示你想要把 $k$ 个形状粘在一起，$\texttt{id}(A_1),\ldots ,\texttt{id}(A_k)$ 是它们的编号，$C_1,\ldots ,C_k$ 是与 $A_1,\ldots A_k$ 等价且在 $B$ 内部的形状，$B$ 是将 $C_1,\ldots ,C_k$ 粘在一起形成的形状。

推荐输出坐标时保留至少 $10$ 位小数。

输出必须满足以下条件：

• 输出的所有点坐标都应该在 $[-10^7,10^7]$ 之内；
• 输出的每个形状最多包含 $100$ 个点；
• 每次操作中，$1\le k\le 100$；
• 操作数不多于 $2\times 10^3$；
• 输出中所有形状的总点数不超过 $2\times 10^4$；
• 在最后，必须有且只有一个形状（未被剪开），并且这个形状必须等价于 $T$；
• 所有操作必须均被 checker 判为合法。如果有精度误差是可以被接受的（在 checker 内部，允许的误差为绝对误差或相对误差不超过 $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

样例说明 1

上图显示了第一个样例输出。左边是用剪刀后的原始形状，在右边的是用胶带粘好后的形状。

样例输入 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

样例输出 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.47000000000 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.47 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

样例说明 3

对于第三个样例，上图展示了输出的三个阶段。首先，我们把输入的矩形切成两个小矩形，然后我们把两个矩形中较大的一个再切成两个。在这个阶段操作之后的状态如图左上部分所示。

接下来，我们把两个新矩形两个新矩形粘起来，形成一个六边形，然后我们把这个多边形切成三个 $2\times 1$ 的矩形和一个小一些的矩形。在这个阶段操作之后的状态如图左下部分所示。

最后，我们被第一步留下的较小的矩形和第二阶段新形成的四个矩形粘在一起，形成一个目标 $3\times 3$ 的正方形。

数据范围与提示

对于所有数据：

• 每个形状包含大于等于 $3$ 个点，但小于等于 $10$ 个点。

• 所有输入的坐标均为整数，并在 $[-10^6,10^6]$ 范围内。

• 对于每个形状，任意三个点构成的角都不小于 $3^\circ$。这包含非连续的点，暗示没有任何三点共线。

• 多边形 $P(S)$ 和 $P(T)$ 面积相同。

一个形状被称为好矩形，如果它的形式为 $((0,0),(x,0),(x,y),(0,y))$，并且 $x,y$ 均为正整数。

一个形状被称为好正方形，如果它的形式为 $((0,0),(x,0),(x,y),(0,y))$，$x,y$ 均为正整数，且 $x=y$。

形状 $A$ 被称为严格凸多边形，如果 $P(A)$ 的内角均小于 $180^\circ$。

在以上定义下，详细子任务分值与附加限制如下表：

子任务编号	附加限制	分值
$1$	$S,T$ 均为好矩形，所有点坐标都在 $[0,10]$ 内	$5$
$2$	$S$ 是好矩形，且 $x>y$，$T$ 是好正方形	$13$
$3$	$S,T$ 均为好矩形	$12$
$4$	$S$ 是三角形，$T$ 是好正方形	$14$
$5$	$S,T$ 均为三角形	$10$
$6$	$S$ 是严格凸多边形，$T$ 是好矩形	$16$
$7$	$T$ 是好矩形	$11$
$8$	无附加限制	$19$