제출 #1183129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183129		anmattroi	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3094 ms	7240 KiB

circle_selection

#include <bits/stdc++.h>
#define maxn 300005
using namespace std;

int n;
int cl[maxn];

struct circle {
    int x, y, r;
} a[maxn];

int intersect(int x, int y) {
    return (1LL * (a[x].x - a[y].x) * (a[x].x - a[y].x) + 1LL * (a[x].y - a[y].y) * (a[x].y - a[y].y))
            <= (1LL * (a[x].r + a[y].r) * (a[x].r + a[y].r));
}

int ans[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].r;

    while (1) {
        if (1) {
            int sum = 0;
            for (int i = 1; i <= n; i++) sum += (cl[i] > 0);
            if (sum == n) break;
        }
        int mxsz = -1, p = 0;
        for (int i = 1; i <= n; i++)
        if (!cl[i] && mxsz < a[i].r) {
            mxsz = a[i].r;
            p = i;
        }
        for (int j = 1; j <= n; j++)
        if (!cl[j] && intersect(p, j)) cl[j] = p;
    }

    for (int i = 1; i <= n; i++) cout << cl[i] << ' ';
}
/*
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
*/

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13