CF1193C.Scissors and Tape

You are given a piece of paper in the shape of a simple polygon $S$. Your task is to turn it into a simple polygon $T$ that has the same area as $S$.

You can use two tools: scissors and tape. Scissors can be used to cut any polygon into smaller polygonal pieces. Tape can be used to combine smaller pieces into larger polygons. You can use each tool multiple times, in any order.

The polygons given in the input have integer coordinates, but you are allowed to produce shapes with non-integer coordinates in your output.

A formal definition of the task follows.

A shape $Q=(Q_0,\dots,Q_{n-1})$ is a sequence of three or more points in the plane such that:

• The closed polyline $Q_0Q_1Q_2\dots Q_{n-1}Q_0$ never touches or intersects itself, and therefore it forms the boundary of a simple polygon.
• The polyline goes around the boundary of the polygon in the counter-clockwise direction.

The polygon whose boundary is the shape $Q$ will be denoted $P(Q)$.

Two shapes are called equivalent if one can be translated and/or rotated to become identical with the other.

Note that mirroring a shape is not allowed. Also note that the order of points matters: the shape $(Q_1,\dots,Q_{n-1},Q_0)$ is not necessarily equivalent to the shape $(Q_0,\dots,Q_{n-1})$.

In the figure on the left: Shapes $U$ and $V$ are equivalent. Shape $W$ is not equivalent with them because the points of $W$ are given in a different order. Regardless of the order of points, the fourth shape is not equivalent with the previous ones either as flipping a shape is not allowed.

In both input and output, a shape with $n$ points is represented as a single line that contains $2n+1$ space-separated numbers: the number $n$ followed by the coordinates of the points: $Q_{0,x}$, $Q_{0,y}$, $Q_{1,x}$, ...

Shapes have identification numbers (IDs). The given shape $S$ has ID 0, the shapes you produce in your solutions are given IDs 1, 2, 3, ..., in the order in which they are produced.

Shapes $B_1,\dots,B_k$ form a subdivision of shape $A$ if:

• The union of all $P(B_i)$ is exactly $P(A)$.
• For each $i\neq j$, the area of the intersection of $P(B_i)$ and $P(B_j)$ is zero.

The scissors operation destroys one existing shape $A$ and produces one or more shapes $B_1,\dots,B_k$ that form a subdivision of $A$.

In the figure: Shape $A$ (square) subdivided into shapes $B_1$, $B_2$, $B_3$ (the three triangles). One valid way to describe one of the $B_i$ is "3 3 1 6 1 5.1 4".

The tape operation destroys one or more existing shapes $A_1,\dots,A_k$ and produces one new shape $B$. In order to perform this operation, you must first specify shapes $C_1,\dots,C_k$ and only then the final shape $B$. These shapes must satisfy the following:

• For each $i$, the shape $C_i$ is equivalent to the shape $A_i$.
• The shapes $C_1,\dots,C_k$ form a subdivision of the shape $B$.

Informally, you choose the shape $B$ and show how to move each of the existing $A_i$ to its correct location $C_i$ within $B$. Note that only the shape $B$ gets a new ID, the shapes $C_i$ do not.

你得到一张形状为简单多边形 $S$ 的纸。你的任务是将其转变为另一个简单多边形 $T$，使得 $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；你在解答中生成的图形按生成顺序依次编号为 1、2、3、……。

图形 $B_1,\dots,B_k$ 构成图形 $A$ 的一个剖分（subdivision），当且仅当满足：

• 所有 $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$ 并不获得新 ID。

The first line contains the source shape $S$.

The second line contains the target shape $T$.

Each shape has between 3 and 10 points, inclusive. Both shapes are given in the format specified above.

All coordinates in the input are integers between $-10^6$ and $10^6$, inclusive.

In each shape, no three points form an angle smaller than 3 degrees. (This includes non-consecutive points and implies that no three points are collinear.)

The polygons $P(S)$ and $P(T)$ have the same area.

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

每个形状包含 3 至 10 个点（含端点）。两个形状均以如上所述的格式给出。

输入中的所有坐标均为介于 $-10^6$ 和 $10^6$（含端点）之间的整数。

在每个形状中，任意三点所构成的角均不小于 3 度。（这包括非相邻的点，且意味着任意三点均不共线。）

多边形 $P(S)$ 与 $P(T)$ 的面积相等。

Whenever you use the scissors operation, output a block of lines of the form:

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

where $id(A)$ is the ID of the shape you want to destroy, $k$ is the number of new shapes you want to produce, and $B_1,\dots,B_k$ are those shapes.

Whenever you use the tape operation, output a block of lines of the form:

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

where $k$ is the number of shapes you want to tape together, $id(A_1),\dots,id(A_k)$ are their IDs, $C_1,\dots,C_k$ are equivalent shapes showing their position within $B$, and $B$ is the final shape obtained by taping them together.

It is recommended to output coordinates of points to at least 10 decimal places.

The output must satisfy the following:

• All coordinates of points in the output must be between $-10^7$ and $10^7$, inclusive.
• Each shape in the output must have at most $100$ points.
• In each operation the number $k$ of shapes must be between $1$ and $100$, inclusive.
• The number of operations must not exceed $2000$.
• The total number of points in all shapes in the output must not exceed $20000$.
• In the end, there must be exactly one shape (that hasn't been destroyed), and that shape must be equivalent to $T$.
• All operations must be valid according to the checker. Solutions with small rounding errors will be accepted. (Internally, all comparisons check for absolute or relative error up to $10^{-3}$ when verifying each condition.)

每次使用剪刀操作时，输出如下格式的若干行：

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

其中 $id(A)$ 是您希望销毁的图形的编号，$k$ 是您希望生成的新图形的数量，$B_1,\dots,B_k$ 即为这些新图形。

每次使用胶带操作时，输出如下格式的若干行：

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

其中 $k$ 是您希望粘合在一起的图形数量，$id(A_1),\dots,id(A_k)$ 是它们的编号，$C_1,\dots,C_k$ 是分别表示它们在 $B$ 中位置的等价图形，$B$ 是通过将这些图形粘合而得到的最终图形。

建议输出点的坐标时保留至少 10 位小数。

输出必须满足以下条件：

• 输出中所有点的坐标值必须在 $[-10^7, 10^7]$ 范围内（含端点）。
• 输出中的每个图形至多包含 $100$ 个点。
• 每次操作中，图形数量 $k$ 必须在 $1$ 到 $100$ 之间（含端点）。
• 操作总数不得超过 $2000$ 次。
• 输出中所有图形的点的总数不得超过 $20000$。
• 最终必须恰好剩余一个未被销毁的图形，且该图形必须与目标图形 $T$ 等价。
• 所有操作必须符合校验器的合法性要求。存在微小舍入误差的解将被接受。（在校验器内部，验证每个条件时，所有比较均允许绝对或相对误差不超过 $10^{-3}$。）

The figure below shows the first example output. On the left is the original figure after using the scissors, on the right are the corresponding $C_i$ when we tape those pieces back together.

In the second example output, note that it is sufficient if the final shape is equivalent to the target one, they do not have to be identical.

The figure below shows three stages of the third example output. First, we cut the input rectangle into two smaller rectangles, then we cut the bigger of those two rectangles into two more. State after these cuts is shown in the top left part of the figure.

Continuing, we tape the two new rectangles together to form a six-sided polygon, and then we cut that polygon into three 2-by-1 rectangles and one smaller rectangle. This is shown in the bottom left part of the figure.

Finally, we take the rectangle we still have from the first step and the four new rectangles and we assemble them into the desired 3-by-3 square.

下图展示了第一个示例的输出结果：左侧为使用剪刀裁剪后的原始图形，右侧为将这些碎片重新粘贴后所对应的 $C_i$。

在第二个示例输出中，请注意：最终形状只需与目标形状等价即可，不必完全相同。

下图展示了第三个示例输出的三个阶段：首先，我们将输入的矩形沿直线裁剪为两个更小的矩形；接着，再将其中较大的那个矩形进一步裁剪为两个矩形。图中左上部分显示了完成上述所有裁剪操作后的状态。

继续操作：我们将新得到的两个矩形粘贴在一起，形成一个六边形；然后将该六边形裁剪为三个 $2\times1$ 的矩形和一个更小的矩形。图中左下部分展示了这一阶段的结果。

最后，我们将第一步中保留下来的矩形与新得到的四个矩形组合拼装，构成所期望的 $3\times3$ 正方形。