P6848 [CEOI 2019] Scissors and Tape

You are given a simple polygon $S$, and you want to transform it into a simple polygon $T$ with the same area. You can use two tools: scissors and tape. Scissors can cut any polygon into smaller polygons. Tape can glue smaller polygons into a larger polygon. You may use each tool any number of times, in any order. All polygon vertices in the input have integer coordinates, but your solution is allowed to create polygons whose vertex coordinates are not integers. The formal definition of the task is as follows: A shape $Q=(Q_0,\ldots Q_{n-1})$ is a sequence of at least three points in the plane such that: - The closed polyline $Q_0,Q_1,Q_2,\ldots Q_{n-1},Q_0$ does not self-intersect. - This polyline goes counterclockwise around the boundary of the polygon. The polygon with boundary given by shape $Q$ is denoted by $P(Q)$. Two shapes are equivalent if and only if one can be translated or rotated to become identical to the other. Reflection is not allowed, and the order of points matters: $(Q_0,Q_1\ldots Q_{n-1})$ is not necessarily equivalent to $(Q_1\ldots Q_{n-1},Q_0)$.  In the figure above, shapes $U$ and $V$ are equivalent, but shape $W$ is not equivalent to them, because the order of the given points is different. In any case, the fourth shape is not identical to any of the first three, because reflection is not allowed. Each shape is represented by $2\times n+1$ numbers. The first number is $n$, the number of points of the shape. Then follow $2\times n$ numbers $Q_{0,x},Q_{0,y},Q_{1,x},\ldots,Q_{n-1,x},Q_{n-1,y}$. Each pair of numbers gives the coordinates of one point in the shape; for example, $(Q_{0,x},Q_{0,y})$ is the coordinate of $Q_0$. Shapes $B_1,B_2,\ldots B_k$ are called a partition of shape $A$ if and only if: - The union of all $P(B_i)$ equals $P(A)$. - For all $i\not=j$, $P(B_i)$ and $P(B_j)$ do not intersect. Shapes have IDs. The ID of $S$ is $0$. The shapes you create in your solution will have IDs $1,2,3,\ldots$. Scissors cut an existing shape $A$ and produce a partition $B_1,B_2,\ldots B_k$ of $A$.  In the figure above, shape $A$ is partitioned into three triangles $B_1,B_2,B_3$. One way to describe the red triangle is `3 3 1 6 1 5.1 4`. Tape can glue existing shapes $A_1,\ldots A_k$ and turn them into a shape $B$. To perform this operation, you must give $C_1,\ldots,C_k$ and the final shape $B$, and satisfy the following requirements: - $C_i$ is equivalent to $A_i$. - $C_1,\ldots,C_k$ form a partition of $B$. Informally, you choose the shape $B$, and then show how to move each existing $A_i$ to its correct position $C_i$ to form $B$. Note that shape $B$ must be assigned a new ID, but the $C_i$ do not need IDs.

The first line is the shape $S$. The second line is the shape $T$.

Each time you use scissors, output in the following format: ``` scissors id(A) k B_1 B_2 ... B_k ``` Each time you use tape, output in the following format: ``` tape k id(A_1) ... id(A_k) C_1 C_2 ... C_k B ``` Your output must satisfy the following constraints: - All point coordinates in the output must be within $[-10^7,10^7]$. - Each shape in the output may have at most $100$ points. - In each operation, $1\le k\le 100$. - The number of operations is at most $2\times 10^3$. - The total number of points across all shapes in the output does not exceed $2\times 10^4$. - In the end, there must be exactly one shape left, and it must be equivalent to $T$.

#### Sample Explanation #### Sample 1 Explanation  The top-left figure is the original shape after the scissors operation, and the right side shows the corresponding $C_i$ after using tape. #### Sample 2 Explanation Note that the target polygon and the polygon you finally obtain only need to be equivalent; they do not need to be exactly the same. #### Sample 3 Explanation The following figure shows the three stages of the output for this sample:  #### Constraints For $100\%$ of the testdata, it is guaranteed that the number of points of $S$ and $T$ is $\le 10$ and $\ge 3$. All input point coordinates are within $[-10^6,10^6]$. No three points are collinear. The areas of $P(S)$ and $P(T)$ are equal. If a shape has vertices $(0,0),(x,0),(0,y),(x,y)$ where $x,y$ are positive integers, then it is called a good rectangle. If a shape is a good rectangle and $x=y$, then it is called a good square. If every interior angle of polygon $P(A)$ is less than $180$ degrees, then shape $A$ is called a strictly convex polygon. The detailed subtask constraints are as follows: | Subtask ID | Constraints | Score | | :-: | :-: | :-: | | 1 | $S$ and $T$ are good rectangles, and all input point coordinates are within $[1,10]$ | $5$ | | 2 | $S$ is a good rectangle and $x>y$, $T$ is a good square | $13$ | | 3 | $S,T$ are good rectangles | $12$ | | 4 | $S$ is a triangle, $T$ is a good square | $14$ | | 5 | $S,T$ are triangles | $10$ | | 6 | $S$ is a strictly convex polygon, $T$ is a good rectangle | $16$ | | 7 | $T$ is a good rectangle | $11$ | | 8 | No special constraints | $19$ | #### Notes This problem is translated from [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 2](https://ceoi.sk/tasks/) [T3 Scissors and Tape](https://ceoi.sk/static/statements/scissors-ENG.pdf)。 Translated by ChatGPT 5