Submission #864632

#	Time	Username	Problem	Language	Result	Execution time	Memory
864632		danikoynov	Circle selection (APIO18_circle_selection)	C++14	7 / 100	145 ms	1116 KiB

circle_selection

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

struct point
{
    ll x, y;
};

struct circle
{
    point centre;
    ll radius;
};

const int maxn = 5010;

int n;
circle c[maxn];

void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> c[i].centre.x >> c[i].centre.y >> c[i].radius;
}

int used[maxn], par[maxn];

int find_biggest()
{
    int idx = -1;
    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;
        if (idx == -1 || c[i].radius > c[idx].radius)
            idx = i;
    }

    return idx;
}

ll distance(point A, point B)
{
    ll dx = (A.x - B.x);
    ll dy = (A.y - B.y);

    return dx * dx + dy * dy;
}
void simulate()
{
    while(true)
    {
        int idx = find_biggest();
        if (idx == -1)
            break;
        ///cout << "current " << idx << endl;
        for (int i = 1; i <= n; i ++)
        {
            if (used[i] == 1)
                continue;
            
            if (distance(c[idx].centre, c[i].centre) <=
                 (c[idx].radius + c[i].radius) * (c[idx].radius + c[i].radius))
                used[i] = 1, par[i] = idx;
        }
        
    }
}

void print()
{
    for (int i = 1; i <= n; i ++)
        cout << par[i] << " ";
    cout << endl;
}

void solve()
{
    input();
    simulate();
    print();
}
int main()
{
    solve();
    return 0;
}

/**
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

*/

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