|
||||||||||
PaperTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 415 Accepted Submission(s): 63 Special Judge Problem Description Jitui and Goddess are taking the Train 38 to see Protein Tiger. Goddess gives Jitui a paper. The paper is a convex polygon. Goddess wants to cut off some circles from the paper. These circles may overlap but will not exceed the paper. The paper may rotate around the select vertex, when Jitui selects a vertex from the paper and hang it on the wall. Given the original coordinates, now Jitui wants to know the coordinates of every vertex when the paper is stable. Input There are several test cases, please process till EOF. The first line contains n, m, p (1 ¡Ü n,m ¡Ü 2000, 1 ¡Ü p ¡Ü n) means number of convex polygon vertex, number of circles and the number of vertex Jitui selects. Next n lines, each line contains two integers x, y (|x|, |y| ¡Ü 10000) means the coordinates of every vertex of the paper. Next m lines, each line contains three integers x, y, r describes a circle radius is r and center is (x, y). The convex polygon will be given in counter-clockwise. Output For each test contains n lines. Describes the coordinates of the paper which is stable. The order should be the same as origin convex polygon. Answer will be considered as correct if their absolute error is less than 10-5. Sample Input
Sample Output
Author Fudan University Source | ||||||||||
|