| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 405406 | saleh | 원 고르기 (APIO18_circle_selection) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 3;
/*
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
*/
int n, x[MAXN], y[MAXN], r[MAXN], par[MAXN];
struct cmp { bool operator ()(int a, int b) { return r[a] > r[b]? true: (r[a] == r[b]? a < b: false); } };
set<int, cmp> s;
auto dis(int a, int b) { return sqrt(abs(x[a] - x[b]) * abs(x[a] - x[b]) + abs(y[a] - y[b]) * abs(y[a] - y[b])); }
bool sect(int a, int b) { return dis(a, b) <= r[a] + r[b]; }
int main() {
cin >> n;
if (n >= MAXN) return 0;
for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> r[i];
for (int i = 0; i < n; i++) s.insert(i);
while (!s.empty()) {
int x = *s.begin();
for (auto i = s.begin(); i != s.end(); ) if (sect(*i, x)) {
par[*i] = x;
i = s.erase(i);
} else i++;
}
for (int i = 0; i < n; i++) cout << par[i] + 1 << ' ';
return 0;
}