2079 . [APIO '18] 選圓圈

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

cwcodinglife

User's AC Ratio

71.4% (10/14)

Submission's AC Ratio

28.6% (24/84)

Tags

APIO 2018-APIO

Description

在平面上，有 n 個圓，記為 c1,c2,…,cn 。我們嘗試對這些圓執行這個演算法：

  1. 找到這些圓中半徑最大的。如果有多個半徑最大的圓，選擇編號最小的。記作 ci 。
  2. 刪除ci 及與其有交集的所有圓。兩個圓有交集若且唯若平面上存在一個點，這個點同時在這兩個圓的圓周上或圓內。（原文直譯：如果平面上存在一個點被這兩個圓所包含，我們稱這兩個圓有交集。一個點被一個圓包含，若且唯若它位於圓內或圓周上。）
  3. 重複上面兩個步驟直到所有的圓都被刪除。

當ci被刪除時，若循環中第1步選擇的圓是cj，我們說ci 被cj刪除。對於每個圓，求出它是被哪一個圓刪除的。

Input Format

第一行包含一个整數 n ，表示開始時平面上圓的數量 (1≤n≤3⋅105)。

接下来 n 行，每行包含三個整數 xi,yi,ri 依序描述圓 ci 圓心的x坐標、y坐標和它的半徑 (−109≤xi,yi≤109, 1≤ri≤109)。

Output Format

輸出一行，包含 n 個整數 a1,a2,...an ，其中 ai 表示圓 ci 是被圓cai 删除的。

Sample Input 1

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

Sample Output 1

7 2 7 4 5 6 7 7 4 7 6

Hints

題目描述中的圖片對應了範例測資中的情況。

Problem Source

APIO 2018 Circle selection

Subtasks

No. Testdata Range Constraints Score
1 0~26 n≤5000 13
2 27~34 n≤3⋅105, 對於所有的圓 yi=0 30
3 35~44 n≤3⋅105, 每個圓最多和一個其他圓有交集。 23
4 45~50 n≤3⋅105, 所有的圓半徑相同。 12
5 51~74 n≤105 7
6 75~116 n≤3⋅105 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1
1 3000 1048576 65536 1
2 3000 1048576 65536 1
3 3000 1048576 65536 1
4 3000 1048576 65536 1
5 3000 1048576 65536 1
6 3000 1048576 65536 1
7 3000 1048576 65536 1
8 3000 1048576 65536 1
9 3000 1048576 65536 1
10 3000 1048576 65536 1
11 3000 1048576 65536 1
12 3000 1048576 65536 1
13 3000 1048576 65536 1
14 3000 1048576 65536 1
15 3000 1048576 65536 1
16 3000 1048576 65536 1
17 3000 1048576 65536 1
18 3000 1048576 65536 1
19 3000 1048576 65536 1
20 3000 1048576 65536 1
21 3000 1048576 65536 1
22 3000 1048576 65536 1
23 3000 1048576 65536 1
24 3000 1048576 65536 1
25 3000 1048576 65536 1
26 3000 1048576 65536 1
27 3000 1048576 65536 2
28 3000 1048576 65536 2
29 3000 1048576 65536 2
30 3000 1048576 65536 2
31 3000 1048576 65536 2
32 3000 1048576 65536 2
33 3000 1048576 65536 2
34 3000 1048576 65536 2
35 3000 1048576 65536 3
36 3000 1048576 65536 3
37 3000 1048576 65536 3
38 3000 1048576 65536 3
39 3000 1048576 65536 3
40 3000 1048576 65536 3
41 3000 1048576 65536 3
42 3000 1048576 65536 3
43 3000 1048576 65536 3
44 3000 1048576 65536 3
45 3000 1048576 65536 4
46 3000 1048576 65536 4
47 3000 1048576 65536 4
48 3000 1048576 65536 4
49 3000 1048576 65536 4
50 3000 1048576 65536 4
51 3000 1048576 65536 5
52 3000 1048576 65536 5
53 3000 1048576 65536 5
54 3000 1048576 65536 5
55 3000 1048576 65536 5
56 3000 1048576 65536 5
57 3000 1048576 65536 5
58 3000 1048576 65536 5
59 3000 1048576 65536 5
60 3000 1048576 65536 5
61 3000 1048576 65536 5
62 3000 1048576 65536 5
63 3000 1048576 65536 5
64 3000 1048576 65536 5
65 3000 1048576 65536 5
66 3000 1048576 65536 5
67 3000 1048576 65536 5
68 3000 1048576 65536 5
69 3000 1048576 65536 5
70 3000 1048576 65536 5
71 3000 1048576 65536 5
72 3000 1048576 65536 5
73 3000 1048576 65536 5
74 3000 1048576 65536 5
75 3000 1048576 65536 6
76 3000 1048576 65536 6
77 3000 1048576 65536 6
78 3000 1048576 65536 6
79 3000 1048576 65536 6
80 3000 1048576 65536 6
81 3000 1048576 65536 6
82 3000 1048576 65536 6
83 3000 1048576 65536 6
84 3000 1048576 65536 6
85 3000 1048576 65536 6
86 3000 1048576 65536 6
87 3000 1048576 65536 6
88 3000 1048576 65536 6
89 3000 1048576 65536 6
90 3000 1048576 65536 6
91 3000 1048576 65536 6
92 3000 1048576 65536 6
93 3000 1048576 65536 6
94 3000 1048576 65536 6
95 3000 1048576 65536 6
96 3000 1048576 65536 6
97 3000 1048576 65536 6
98 3000 1048576 65536 6
99 3000 1048576 65536 6
100 3000 1048576 65536 6
101 3000 1048576 65536 6
102 3000 1048576 65536 6
103 3000 1048576 65536 6
104 3000 1048576 65536 6
105 3000 1048576 65536 6
106 3000 1048576 65536 6
107 3000 1048576 65536 6
108 3000 1048576 65536 6
109 3000 1048576 65536 6
110 3000 1048576 65536 6
111 3000 1048576 65536 6
112 3000 1048576 65536 6
113 3000 1048576 65536 6
114 3000 1048576 65536 6
115 3000 1048576 65536 6
116 3000 1048576 65536 6
Submit
Back to Top