2079 . [APIO '18] 選圓圈

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 8qbfbv4
baluteshih

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

50.0% (5/10)

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

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

7 2 7 4 5 6 7 7 4 7 6

Hints

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

子任務分數輸入限制
07 $n \leq 5000$
1 12 $n \le 3 \cdot 10^ 5$, 對於所有的圓 $y_i=0$
2 15 $n \le 3 \cdot 10^ 5$, 每個圓最多和一個其他圓有交集。
3 23$n \le 3 \cdot 10^ 5$, 所有的圓半徑相同。
4 30 $n \le 10^ 5$
5 13 $n \le 3 \cdot 10^ 5$

Problem Source

APIO 2018 Circle selection

Subtasks

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