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.

A shape is called a nice rectangle if it has the form $$$((0,0),~ (x,0),~ (x,y),~ (0,y))$$$ for some positive integers $$$x$$$ and $$$y$$$.

A shape is called a nice square if additionally $$$x=y$$$.

A shape $$$A$$$ is called strictly convex if all inner angles of the polygon $$$P(A)$$$ are smaller than 180 degrees.

Subtask 1 (5 points): $$$S$$$ and $$$T$$$ are nice rectangles. All coordinates of all points are integers between 0 and 10, inclusive

Subtask 2 (13 points): $$$S$$$ is a nice rectangle with $$$x>y$$$, and $$$T$$$ is a nice square

Subtask 3 (12 points): $$$S$$$ and $$$T$$$ are nice rectangles

Subtask 4 (14 points): $$$S$$$ is a triangle and $$$T$$$ is a nice square

Subtask 5 (10 points): $$$S$$$ and $$$T$$$ are triangles

Subtask 6 (16 points): $$$S$$$ is a strictly convex polygon and $$$T$$$ is a nice rectangle

Subtask 7 (11 points): $$$T$$$ is a nice rectangle

Subtask 8 (19 points): no additional constraints