제출 #1292640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292640		Hamed_Ghaffari	원 고르기 (APIO18_circle_selection)	C++20	0 / 100	3095 ms	14544 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int ll

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 3e5+5;

struct circle {
    int x, y, r, id;
};

bool isect(circle &c1, circle &c2) {
    ll x = c1.x - c2.x;
    ll y = c1.y - c2.y;
    return 1ll*(c1.r+c2.r)*(c1.r+c2.r) >= x*x + y*y;
}

int n, ans[MXN];
circle c[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].r;
        c[i].x += 1e9;
        c[i].id = i;
    }
    sort(c, c+n, [&](circle c1, circle c2) {
        return c1.r > c2.r || (c1.r == c2.r && c1.id < c2.id);
    });
    vector<circle> vec;
    for(int i=0; i<n; i++) {
        int tmp = -1;
        for(auto &c2 : vec)
            if(isect(c2, c[i]))
                tmp = c2.id;
        if(tmp==-1) {
            ans[c[i].id] = c[i].id;
            vec.push_back(c[i]);
        }
        else ans[c[i].id] = tmp;
    }
    for(int i=0; i<n; i++) cout << ans[i]+1 << ' ';
    cout << '\n';
    return 0;
}

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