You are given a piece of paper in the shape of a simple polygon . Your task is to turn it into a simple polygon
that has the same area as
.
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 is a sequence of three or more points in the plane such that:
- The closed polyline
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 will be denoted
.
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
is not necessarily equivalent to the shape
.
In the figure above: Shapes and
are
equivalent. Shape
is not equivalent with
them because the points of
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 points is represented as a single line that contains
space-separated
numbers: the number
followed by the coordinates of the points:
Shapes have identification numbers (IDs). The given shape has ID
, the shapes you produce in your solutions
are given IDs
, in the order in which they are produced.
Shapes form a subdivision of shape
if:
- The union of all
is exactly
.
- For each
, the area of the intersection of
and
is zero.
The scissors operation destroys one existing shape and produces one or more shapes
that form a
subdivision of
.
In the figure above: Shape (square) subdivided into shapes
(the
three triangles). One valid way to describe one of the
is
.
The tape operation destroys one or more existing shapes and produces one new shape
. In order to
perform this operation, you must first specify shapes
and only then the final shape
. These shapes
must satisfy the following:
- For each
, the shape
is equivalent to the shape
.
- The shapes
form a subdivision of the shape
.
Informally, you choose the shape and show how to move each of the existing
to its correct location
within
. Note that only the shape
gets a new ID, the shapes
do not.
Input
The first line contains the source shape .
The second line contains the target shape .
Each shape has between and
points, inclusive. Both shapes are given in the format specified above.
All coordinates in the input are integers between and
, inclusive.
In each shape, no three points form an angle smaller than degrees. (This includes non-consecutive points and
implies that no three points are collinear.)
The polygons and
have the same area.
Output
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 is the ID of the shape you want to destroy,
is the number of new shapes you want to produce, and
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 is the number of shapes you want to tape together,
are their IDs,
are
equivalent shapes showing their position within
, and
is the final shape obtained by taping them together.
It is recommended to output coordinates of points to at least decimal places.
The output must satisfy the following:
- All coordinates of points in the output must be between
and
, inclusive.
- Each shape in the output must have at most
points.
- In each operation the number
of shapes must be between
and
, inclusive.
- The number of operations must not exceed
.
- The total number of points in all shapes in the output must not exceed
.
- In the end, there must be exactly one shape (that hasn't been destroyed), and that shape must be equivalent
to
.
- 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
when verifying each condition.)
Scoring
A shape is called a nice rectangle if it has the form for positive integers
and
.
A shape is called a nice square if additionally .
A shape is called strictly convex if all inner angles of the polygon P(A) are smaller than
degrees.
Subtask (
points):
and
are nice rectangles. All coordinates of all points are integers between
and
,
inclusive
Subtask (
points):
is a nice rectangle with
, and
is a nice square
Subtask (
points):
and
are nice rectangles
Subtask (
points):
is a triangle and
is a nice square
Subtask (
points):
and
are triangles
Subtask (
points):
is a strictly convex polygon and
is a nice rectangle
Subtask (
points):
is a nice rectangle
Subtask (
points): no additional constraints
Sample Input 1
6 0 0 6 0 6 4 5 4 5 9 0 9
4 0 0 7 0 7 7 0 7
Sample Output 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
Sample Input 2
4 0 0 3 0 3 3 0 3
4 7 -1 10 -1 11 2 8 2
Sample Output 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
Sample Input 3
4 0 0 9 0 9 1 0 1
4 0 0 3 0 3 3 0 3
Sample Output 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
Note
The figure above shows the first example output. On the left is the original
figure after using the scissors, on the right are the corresponding 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.
Comments