#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MAX = 3e5 + 9;
int N, par[MAX];
bool removed[MAX];
struct Circle {
i64 x, y;
i64 radius;
int index;
} circles[MAX], sweep[MAX];
pair<int, int> seg[MAX];
bool cmpX(Circle& a, Circle& b) {
if (a.x == b.x) return a.radius > b.radius;
return a.x < b.x;
}
bool intercept(Circle& a, Circle& b) {
i64 dx = a.x - b.x;
i64 dy = a.y - b.y;
i64 dist2 = dx * dx * 1LL + dy * dy * 1LL;
i64 r2 = (a.radius * 1LL + b.radius * 1LL) * (a.radius * 1LL + b.radius * 1LL) * 1LL;
if (dist2 <= r2) {
return true;
} else {
return false;
}
}
int find_intercept_left(Circle& rhs, int low, int high) {
if (low == high)
return low;
int mid = (low + high) / 2;
if (intercept(rhs, sweep[mid])) {
return find_intercept_left(rhs, low, mid);
} else {
return find_intercept_left(rhs, mid + 1, high);
}
}
int find_intercept_right(Circle& rhs, int low, int high) {
if (low == high)
return low;
int mid = (low + high + 1) / 2;
if (intercept(rhs, sweep[mid])) {
return find_intercept_right(rhs, mid, high);
} else {
return find_intercept_right(rhs, low, mid - 1);
}
}
bool cmp(Circle& a, Circle& b) {
if (a.radius == b.radius)
return a.x < b.x;
return a.radius > b.radius;
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
scanf("%lld%lld%lld", &circles[i].x, &circles[i].y, &circles[i].radius);
circles[i].index = i;
}
for (int i = 0; i < N; ++i)
sweep[i] = circles[i];
sort(sweep, sweep + N, cmpX);
for (int i = 0; i < N; ++i) {
int u = sweep[i].index;
if (i == 0) {
seg[u].first = i;
seg[u].second = find_intercept_right(sweep[i], i, N - 1);
} else if (i == N - 1) {
seg[u].first = find_intercept_left(sweep[i], 0, i);
seg[u].second = N - 1;
} else {
seg[u].first = find_intercept_left(sweep[i], 0, i);
seg[u].second = find_intercept_right(sweep[i], i, N - 1);
}
}
// for (int i = 0; i < N; ++i) {
// printf("%d/%d/%d ", sweep[i].index + 1, seg[i].first, seg[i].second);
// }
// printf("\n");
sort(circles, circles + N, cmp);
for (int i = 0; i < N; ++i)
removed[i] = false;
for (int i = 0; i < N; ++i) {
int u = circles[i].index;
if (removed[u])
continue;
par[u] = u;
for (int j = seg[u].first; j <= seg[u].second; ++j) {
int v = sweep[j].index;
if (removed[v])
continue;
par[v] = u;
removed[v] = true;
}
removed[u] = true;
}
for (int i = 0; i < N; ++i) {
printf("%d ", par[i] + 1);
}
printf("\n");
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
circle_selection.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%lld%lld%lld", &circles[i].x, &circles[i].y, &circles[i].radius);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
359 ms |
31628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
287 ms |
32676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |