Submission #477100

#	Time	Username	Problem	Language	Result	Execution time	Memory
477100		khr03ae	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3089 ms	18876 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

const int MAX = 3e5 + 9;

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

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

bool cmp(int i, int j) {
    if (C[i].rad == C[j].rad) return i < j;
    return C[i].rad > C[j].rad;
}

bool intercept(int i, int j) {
    i64 dx = 1LL * C[i].x - 1LL * C[j].x;
    i64 dy = 1LL * C[i].y - 1LL * C[j].y;
    i64 dist2 = 1LL * dx * dx + 1LL * dy * dy;
    i64 rad2 = 1LL * (C[i].rad + C[j].rad) * (C[i].rad + C[j].rad);
    return dist2 <= rad2;
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%lld%lld%lld", &C[i].x, &C[i].y, &C[i].rad);
    }
    
    // Initialize
    for (int i = 0; i < N; ++i) {
        sorted[i] = i;
        deleted[i] = false;
    }

    sort(sorted, sorted + N, cmp);
    
    for (int i = 0; i < N; ++i) {
        int u = sorted[i];
        if (deleted[u]) continue;
        for (int j = i + 1; j < N; ++j) {
            int v = sorted[j];
            if (deleted[v]) continue;
            if (intercept(u, v)) {
                par[v] = u;
                deleted[v] = true;
            }
        }
        par[u] = u;
        deleted[u] = true;
    }

    for (int i = 0; i < N; ++i) {
        printf("%d ", par[i] + 1);
    }
    puts("\n");
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld%lld%lld", &C[i].x, &C[i].y, &C[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