Submission #382132

#	Time	Username	Problem	Language	Result	Execution time	Memory
382132		mohamedsobhi777	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3083 ms	13260 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;

int n;
bool act[N];

struct circle
{
       int x, y, r, j;
       circle(int _x, int _y, int _r) : x(_x), y(_y), r(_r) {}
       bool operator<(circle &ohs)
       {
              return make_pair(-r, j) < make_pair(-ohs.r, ohs.j);
       }
       bool intersect(circle ohs)
       {
              double dist = hypot(x - ohs.x, y - ohs.y);
              double rr = r + ohs.r;
              return dist <= rr;
       }
};

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;

       vector<circle> v;

       for (int i = 0; i < n; ++i)
       {
              int x, y, r;
              cin >> x >> y >> r;
              v.pb(circle(x, y, r));
              v.back().j = i;
       }

       sort(all(v));
       vi ans(n);

       for (int i = 0; i < n; ++i)
       {
              if (act[i])
                     continue;
              ans[v[i].j] = v[i].j + 1;
              act[i] = 1;
              for (int j = 0; j < n; ++j)
              {
                     if (i == j)
                            continue;
                     if (!act[j] && v[i].intersect(v[j]))
                     {
                            ans[v[j].j] = v[i].j + 1;
                            act[j] = 1;
                     }
              }
       }

       for (auto u : ans)
              cout << u << " ";
       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