在平面上,有 $n$ 個圓,記為 $c_1, c_2, \ldots, c_n$ 。我們嘗試對這些圓執行這個演算法:
第一行包含一个整數 $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$)。
輸出一行,包含 $n$ 個整數 $a_1, a_2, ... a_n$ ,其中 $a_i$ 表示圓 $c_i$ 是被圓$c_{a_i}$ 删除的。
題目描述中的圖片對應了範例測資中的情況。
APIO 2018 Circle selection
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 |