Submission #1160974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160974		not_amir	원 고르기 (APIO18_circle_selection)	C++20	0 / 100	211 ms	10452 KiB

circle_selection

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

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

bool intersect(circle a, circle b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) <= (a.r + b.r) * (a.r + b.r);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<circle> c(n);
    for (int i = 0; i < n; i++)
        cin >> c[i].x >> c[i].y >> c[i].r;
    vector<array<int, 3>> cmp(n);
    int r = c[0].r;
    for (int i = 0; i < n; i++)
        cmp[i] = {c[i].x / (2 * r), c[i].y / (2 * r), i};
    sort(cmp.begin(), cmp.end());
    vector ans(n, - 1);
    for (int i = 0; i < n; i++) {
        if (ans[i] >= 0)
            continue;
        ans[i] = i;
        int cx = c[i].x / (2 * r), cy = c[i].y / (2 * r);
        for (int x = cx - 1; x <= cx + 1; x++) {
            auto it = lower_bound(cmp.begin(), cmp.end(), array<int, 3>({x, cy - 1, -1}));
            while (it != cmp.end() && (*it)[0] == x && (*it)[1] <= cy + 1) {
                if (ans[(*it)[2]] == -1 && intersect(c[(*it)[2]], c[i]))
                    ans[(*it)[2]] = i;
                it++;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] + 1 << " ";
}

/*
3
0 0 3
1 2 3
2 2 3
*/

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