#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 3e5+5, MOD = 1e9;
struct circle {int x, y, r, i;};
struct event {int t, x, y, i;};
bool operator<(circle a, circle b) {if (a.r == b.r) return a.i < b.i; return a.r > b.r;};
bool operator<(event a, event b) {return (a.t == b.t? (a.i%3 == b.i%3?a.i/3 < b.i/3: a.i%3 < b.i%3) : a.t < b.t);}
int p[M], R[M];
int sq(int a) {return a*a;}
int dist(int x1, int y1, int x2, int y2) {
return sq(x1-x2) + sq(y1-y2);
}
int dist(circle a, circle b) {
return sq(a.x-b.x) + sq(a.y-b.y);
}
vector<circle> dnc(vector<circle> v) {
if (v.size() <= 1) return v;
vector<circle> a, b;
int n = v.size(), m = n/2;
for (int i = 0; i < m; i++) a.push_back(v[i]);
for (int i = m; i < n; i++) b.push_back(v[i]);
a = dnc(a);
vector<event> timeline;
for (auto [x, y, r, i]:b) timeline.push_back({x-r, x, y, 3*i + 1}), timeline.push_back({x+r, x, y, 3*i + 1});
for (auto [x, y, r, i]:a) timeline.push_back({x-r, x, y, 3*i + 0}), timeline.push_back({x+r, x, y, 3*i + 2});
sort(timeline.begin(), timeline.end());
vector<circle> end;
multiset<circle> st;
for (auto [t, x, y, i]:timeline) {
if (i%3 == 0) st.insert({x, y, x-t, i/3});
else if (i%3 == 1) {
i /= 3;
int r = abs(t-x);
int sz = (p[i]>M?0:R[p[i]]);
for (auto [x2, y2, r2, i2]:st) {
if (dist(x, y, x2, y2) <= sq(r + r2)) {
if (r2 > sz) sz = r2, p[i] = i2;
else if (r2 == sz) p[i] = min(i2, p[i]);
}
}
if (p[i]>M && t > x) end.push_back({x, y, r, i});
} else st.erase({x, y, t-x, i/3});
}
end = dnc(end);
for (auto i:a) end.push_back(i);
return end;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
srand(time(0));
int n;
cin >> n;
vector<circle> v;
for (int i = 1; i <= n; i++) {
p[i] = INT_MAX;
int x, y, r;
cin >> x >> y >> r;
R[i] = r;
v.push_back({x, y, r, i});
} sort(v.begin(), v.end());
for (auto [a, b, c, i]:dnc(v)) p[i] = i;
for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
return 0;
}
/*
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
-------
5
1 11 10
12 17 4
19 27 6
13 13 5
24 10 10
--------
1 1 3 1 5
*/
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:78:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
78 | for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
| ^~~
circle_selection.cpp:78:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
78 | for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
73240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
396 ms |
36700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1272 ms |
128520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
