Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Kingdom Partitioning
Description The Kingdom of Qari was conquered, and now 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⁄ Your task is to propose a partitioning that satisfies all Input The first line of the input file contains an integer number The first line of each section contains an integer number m ≤ 30) — the number of circles indicated by _{i}i-th Kingdom. It is followed by m lines describing circles, one circle per line. A circle is described by three integer numbers _{i}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.Output Write to the output file descriptions of Each description shall start with a line that contains a single integer number k ≤ 1000) — the number of vertices in the polygon, followed by _{i}k lines with _{i}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.Sample Input 3 2 0 0 2 7 0 2 1 4 0 2 1 4 0 2 Sample Output 4 2.0 2.0 -2.0 2.0 -2.0 -2.0 2.0 -2.0 4 2.0 0.0 6.0 0.0 6.0 2.0 2.0 2.0 4 2.0 0.0 6.0 0.0 6.0 -2.0 2.0 -2.0 Hint 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. Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator