#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef complex<long double> C;
const int MX = 3e5 + 100;
const double EPS = 1e-5;
struct circle { C p; int r, i; } v[MX];
int ans[MX];
bool touch(int a, int b) {
return !ans[b] and abs(v[b].p - v[a].p) <= v[a].r + v[b].r;
}
main () {
srand(time(0));
int n; cin >> n;
for(int i = 1; i <= n; i ++) {
int x, y, r; cin >> x >> y >> r;
v[i] = {{x, y}, r, i};
}
double ang = rand() * 0.0001;
for(int i = 1; i <= n; i ++) v[i].p *= C{cos(ang), sin(ang)};
sort(v + 1, v + 1 + n, [](circle a, circle b) { return a.p.X < b.p.X; });
priority_queue<pair<int, pii> > pq;
for(int i = 1; i <= n; i ++) pq.push({v[i].r, {-v[i].i, -i}});
while(pq.size()) {
int p = -pq.top().S.S; pq.pop();
if(ans[v[p].i]) continue;
for(int i = max(1, p - 1000); i <= min(n, p + 1000); i ++) {
if(!ans[v[i].i] and abs(v[p].p - v[i].p) - EPS <= v[p].r + v[i].r) ans[v[i].i] = v[p].i;
}
}
for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';
}
Compilation message
circle_selection.cpp:16:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:21:23: warning: narrowing conversion of 'x' from 'int' to 'long double' inside { } [-Wnarrowing]
v[i] = {{x, y}, r, i};
^
circle_selection.cpp:21:23: warning: narrowing conversion of 'y' from 'int' to 'long double' inside { } [-Wnarrowing]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
13 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14592 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 16 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 19 |
Incorrect |
24 ms |
14564 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
596 ms |
21344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 2 |
Execution timed out |
3026 ms |
16156 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3051 ms |
20712 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
13 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14592 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 16 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 19 |
Incorrect |
24 ms |
14564 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
13 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14592 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 16 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 19 |
Incorrect |
24 ms |
14564 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
