제출 #1292643

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

circle_selection

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

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

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;
    
    // Input the circles
    for (int i = 0; i < n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].r;
        c[i].x += 1e9;  // To avoid negative coordinates
        c[i].id = i;
    }

    // Sort circles by radius (descending), then by id (ascending)
    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 each circle, find the first intersecting circle
    for (int i = 0; i < n; i++) {
        int tmp = -1;
        for (auto &c2 : vec) {
            if (isect(c2, c[i])) {
                tmp = c2.id;
                break;  // Stop once we find the first intersecting circle
            }
        }
        
        // If no intersection is found, assign itself as its answer
        if (tmp == -1) {
            ans[c[i].id] = c[i].id;
            vec.push_back(c[i]);
        } else {
            ans[c[i].id] = tmp;
        }
    }

    // Output results with 1-based indexing
    for (int i = 0; i < n; i++) {
        cout << ans[i] + 1 << ' ';  // Output 1-based index
    }
    cout << '\n';
    
    return 0;
}

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