P5790 [CTSC2006] Jigsaw Puzzle "SPJ Missing"

Little $P$, who is $5$ years old, is very interested in paper cutting. He always likes to cut a rectangular piece of paper into one convex polygon after another. However, after each cutting, he always suspects that he has lost some pieces. Being smart, he came up with a way to check whether any pieces were lost: he puts these convex polygons together, and if they can form a rectangle, he believes that no piece was lost. Since the number of pieces is not large, this work is not difficult. But over time, he lost interest in doing it, so he came to you and hopes that you can tell him whether these convex polygon pieces can be assembled into a rectangle.

The first line contains one positive integer $n$, indicating the number of convex polygons. The following $n$ lines each describe one convex polygon in the format below: On line $i+1$, the first number $m_i$ is the number of vertices of the convex polygon. Then there are $m_i$ pairs of real numbers, where each pair gives the coordinates of a vertex. These $m_i$ vertices are given in counterclockwise order starting from any vertex. All real numbers are in the range $(-10^3,10^3)$, with at most $8$ digits after the decimal point.

If the polygons cannot be assembled into a rectangle, output one line containing `No`. If they can be assembled into a rectangle, the first line should be `Yes`. The next $n$ lines describe the assembly. If they can form an $X\times Y$ rectangle, then the coordinates of the rectangle’s four vertices are $(0,0), (0,Y), (X,Y), (X,0)$. In these $n$ lines, output the coordinates of the vertices of each convex polygon (after assembling into the rectangle). Output in the input order, i.e., the first polygon in the output corresponds to the first polygon in the input. For each polygon, the output order should also match the input order, i.e., the first output vertex corresponds to the first input vertex of that polygon. Therefore, there are $n$ output lines in total, and line $i$ contains $m_i$ pairs of numbers.

#### Sample Explanation In the figure below, the top-left, top-right, and bottom-left parts show the input convex polygons, and the bottom-right part shows the output rectangle.  #### Note Because the two sides of the rectangular paper have different colors, each piece can only be rotated and translated, but cannot be flipped. Therefore, the output $m_i$ vertices should also be in counterclockwise order. #### Constraints For $100\%$ of the testdata, $1\leq n\leq 8$, $3\leq m_i\leq 8$. #### Scoring Two real numbers are considered equal if the absolute value of their difference is less than $10^{-7}$. Translated by ChatGPT 5