#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];
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 cnt;
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]);
int tmp = ++cnt;
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);
for (auto [x2, y2, r2, i2]:st)
if (dist(x, y, x2, y2) <= sq(r + r2))
p[i] = max(p[i], i2);
if (!p[i] && 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);
int n;
cin >> n;
vector<circle> v;
for (int i = 1; i <= n; i++) {
int x, y, r;
cin >> x >> y >> r;
v.push_back({x, y, r, i});
} sort(v.begin(), v.end());
// for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl;
for (auto [a, b, c, i]:dnc(v)) p[i] = i;
// dnc(v);
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
-------
7
0 0 2
-1 0 1
0 0 1
1 0 1
10 0 5
11 0 5
50 0 1
-------
7
1
3
4 8 10
2 5 6 9 11
*/
Compilation message
circle_selection.cpp: In function 'std::vector<circle> dnc(std::vector<circle>)':
circle_selection.cpp:28:9: warning: unused variable 'tmp' [-Wunused-variable]
28 | int tmp = ++cnt;
| ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:73:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
73 | for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
| ^~~
circle_selection.cpp:73:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
73 | 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 |
0 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 |
224 ms |
71020 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 |
Incorrect |
423 ms |
35840 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1241 ms |
124060 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 |
0 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 |
0 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 |
- |
