3592번 - Kingdom Partitioning 스페셜 저지다국어

The Kingdom of Qari was conquered, and now n other Kingdoms are dividing its territory among themselves. However, each Kingdom has its own opinion on which parts of Qari’s land are better. For example, Napaj might want a large open space for settlement while Acirema is only interested in rich oilfields.

To formalize their claims each Kingdom has indicated an area that it considers worthy. An area indicated by each Kingdom is a union of non-overlapping circles. A Kingdom is content with Qari’s partitioning if it receives at least 1/n of the area it has indicated as worthy.

Your task is to propose a partitioning that satisfies all n Kingdoms. In your partitioning an area given to each Kingdom must be a convex polygon with at most 1000 vertices. In this problem it is always possible to find such partitioning.

The first line of the input file contains an integer number n (1 ≤ n ≤ 30) — the number of Kingdoms that are dividing Qari. Then follow n sections describing the areas that were indicated by each Kingdom as worthy.

The first line of each section contains an integer number m_i (1 ≤ m_i ≤ 30) — the number of circles indicated by i-th Kingdom. It is followed by m_i lines describing circles, one circle per line. A circle is described by three integer numbers x, y, and r (−1000 ≤ x, y ≤ 1000; 1 ≤ r ≤ 1000) — the coordinates of its center and its radius correspondingly. Circles in one section do not intersect, but may touch each other.

Write to the output file descriptions of n non-intersecting convex polygons — one for each Kingdom in the same order as in the input file. Polygons may touch each other (see sample output).

Each description shall start with a line that contains a single integer number k_i (3 ≤ k_i ≤ 1000) — the number of vertices in the polygon, followed by k_i lines with x and y coordinates of the vertices (−3000 ≤ x, y ≤ 3000). Coordinates must be precise up to 7 digits after decimal point. The vertices must be listed in either clockwise or counterclockwise direction. No three consecutive vertices are allowed to lie on the same straight line.

On the example picture above, the first Kingdom has indicated as worthy a union of circles 1' and 1''. The second and the third Kingdoms have both indicated the circle marked with 2 and 3 as worthy. One of the possible partitionings is pictured with dashed lines — the first Kingdom will receive a square area around circle 1' while the second and the third Kingdoms will receive rectangles 2 and 3, thus getting an equal share of their indicated area. With this partitioning each Kingdom gets half of the area it has indicated as worthy, which is more than one third required by the problem statement.