Submission #476574

#	Time	Username	Problem	Language	Result	Execution time	Memory
476574		hongrae03k	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3081 ms	19992 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

const int MAX = 3e5 + 9;

struct Circle {
    i64 x, y;
    i64 rad, idx;
} circles[MAX];

bool cmpRad(Circle& a, Circle& b) {
    if (a.rad == b.rad) return a.idx < b.idx;
    return a.rad > b.rad;
}

bool intercept(Circle& a, Circle &b) {
    i64 dx = a.x * 1LL - b.x * 1LL;
    i64 dy = a.y * 1LL - b.y * 1LL;
    i64 dist2 = dx * dx * 1LL + dy * dy * 1LL;
    i64 rad2 = (a.rad + b.rad) * (a.rad + b.rad) * 1LL;
    return dist2 <= rad2;
}

int par[MAX];
bool deleted[MAX];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%lld%lld%lld", &circles[i].x, &circles[i].y, &circles[i].rad);
        circles[i].idx = i;
    }
    sort(circles, circles + N, cmpRad);
    for (int i = 0; i < N; ++i) {
        deleted[i] = false;
    }
    for (int i = 0; i < N; ++i) {
        int u = circles[i].idx;
        if (deleted[u]) continue;
        par[u] = u;
        for (int j = i + 1; j < N; ++j) {
            int v = circles[j].idx;
            if (deleted[v]) continue;
            if (intercept(circles[i], circles[j])) {
                par[v] = u;
                deleted[v] = true;
            }
        }
        deleted[u] = true;
    }
    for (int i = 0; i < N; ++i) {
        printf("%d ", par[i] + 1);
    }
    printf("\n");
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%lld%lld%lld", &circles[i].x, &circles[i].y, &circles[i].rad);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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