# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1173363 | Halym2007 | Circle selection (APIO18_circle_selection) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 3e5 + 5;
int n, x[N], y[N], r[N], vis[N], jog[N];
int main () {
// freopen ("input.txt", "r", stdin);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i] >> r[i];
}
for (int i = 1; i <= n; ++i) {
pii x1 = {-1, -1};
for (int j = 1; j <= n; ++j) {
if (vis[j]) continue;
if (r[j] > x1.ff) {
x1 = {r[j], j};
}
}
if (~x1.ff) {
vis[x1.ss] = 1;
jog[x1.ss] = x1.ss;
for (int j = 1; j <= n; ++j) {
if (vis[j]) continue;
ll kk = abs (x[x1.ss] - x[j]) * abs (x[x1.ss] - x[j]);
ll kk1 = abs (y[x1.ss] - y[j]) * abs (y[x1.ss] - y[j]);
ll kk2 = r[x1.ss] + r[j];
if (ceil(sqrtl(kk1 + k)) <= kk2) {
vis[j] = 1;
jog[j] = x1.ss;
}
}
}
else break;
}
for (int i = 1; i <= n; ++i) {
cout << jog[i] << " ";
}
cout << "\n";
}
/*
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
*/