2079 . [APIO '18] 選圓圈

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

cwcodinglife

User's AC Ratio

76.9% (10/13)

Submission's AC Ratio

32.0% (24/75)

Tags

APIO 2018-APIO

Description

在平面上，有 $n$ 個圓，記為 $c_1, c_2, \ldots, c_n$ 。我們嘗試對這些圓執行這個演算法：

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

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

Input Format

第一行包含一个整數 $n$ ，表示開始時平面上圓的數量 ($1 \le n \le 3 \cdot 10^ 5$)。

接下来 $n$ 行，每行包含三個整數 $x_i, y_i, r_i$ 依序描述圓 $c_i$ 圓心的x坐標、y坐標和它的半徑 ($-10^ 9 \le x_i, y_i\le 10^ 9$, $1\le r_i\le 10^ 9$)。

Output Format

輸出一行，包含 $n$ 個整數 $a_1, a_2, ... a_n$ ，其中 $a_i$ 表示圓 $c_i$ 是被圓$c_{a_i}$ 删除的。

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 \leq 5000$ 13
2 27~34 $n \le 3 \cdot 10^ 5$, 對於所有的圓 $y_i=0$ 30
3 35~44 $n \le 3 \cdot 10^ 5$, 每個圓最多和一個其他圓有交集。 23
4 45~50 $n \le 3 \cdot 10^ 5$, 所有的圓半徑相同。 12
5 51~74 $n \le 10^ 5$ 7
6 75~116 $n \le 3 \cdot 10^ 5$ 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