//https://oj.uz/submission/829851 + gemini #include <bits/stdc++.h> using namespace std; #define y1 ___y1 typedef long long ll; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const int inf = 1e9 + 333; const ll linf = 1e18 + 333; const double EPS = 1e-9; const int N = 3e5 + 5; const double ANG = 2.345; const double COS_A = cos(ANG); const double SIN_A = sin(ANG); pdd rotate(ll x, ll y) { return {x * COS_A - y * SIN_A, x * SIN_A + y * COS_A}; } class tree { public: double x, y, x1, y1, x2, y2; int idx; int alive, sum; tree *l, *r; tree() { x = y = x1 = y1 = x2 = y2 = 0; idx = -1; alive = sum = 0; l = r = 0; } }; typedef tree *pTree; int n; double q_x1, q_y1, q_x2, q_y2; ll x1_dummy, y1_dummy, x2_dummy, y2_dummy; ll k; pair<pdd, int> a[N]; bool cmp(pair<pdd, int> x, pair<pdd, int> y) { if (abs(x.first.second - y.first.second) < EPS) return x.first.first < y.first.first; return x.first.second < y.first.second; } void init(pTree t, int l, int r, bool d = 0) { int m = (l + r) >> 1; if (!d) nth_element(a + l, a + m, a + r + 1); else nth_element(a + l, a + m, a + r + 1, cmp); t->x = t->x1 = t->x2 = a[m].first.first; t->y = t->y1 = t->y2 = a[m].first.second; t->idx = a[m].second; t->alive = t->sum = 1; if (l < m) { if (!t->l) t->l = new tree; init(t->l, l, m - 1, !d); t->sum += t->l->sum; t->x1 = min(t->x1, t->l->x1); t->y1 = min(t->y1, t->l->y1); t->x2 = max(t->x2, t->l->x2); t->y2 = max(t->y2, t->l->y2); } if (m < r) { if (!t->r) t->r = new tree; init(t->r, m + 1, r, !d); t->sum += t->r->sum; t->x1 = min(t->x1, t->r->x1); t->y1 = min(t->y1, t->r->y1); t->x2 = max(t->x2, t->r->x2); t->y2 = max(t->y2, t->r->y2); } } ll X[N], Y[N], R[N]; int ord[N], ans[N]; bool check_intersection(ll x1, ll y1, ll r1, ll x2, ll y2, ll r2) { return (ll) (x1 - x2) * (x1 - x2) + (ll) (y1 - y2) * (y1 - y2) <= (ll) (r1 + r2) * (r1 + r2); } ll ox, oy, o_r; int oid; void query(pTree t) { if (q_x2 < t->x1 - EPS or t->x2 < q_x1 + EPS or q_y2 < t->y1 - EPS or t->y2 < q_y1 + EPS) return; if(t->alive and check_intersection(ox, oy, o_r, X[t->idx], Y[t->idx], R[t->idx])) { ans[t->idx] = oid; t->alive = 0; } if (t->l && t->l->sum > 0) query(t->l); if (t->r && t->r->sum > 0) query(t->r); t->sum = (t->l ? t->l->sum : 0) + (t->r ? t->r->sum : 0) + t->alive; } pTree t; void calculate(ll x, ll y, ll r, int id) { ox = x; oy = y; o_r = r; oid = id; pdd rot_center = rotate(x, y); double search_r = 2.0 * r + EPS; ::q_x1 = rot_center.first - search_r; ::q_y1 = rot_center.second - search_r; ::q_x2 = rot_center.first + search_r; ::q_y2 = rot_center.second + search_r; query(t); } int main() { memset(ans, -1, sizeof(ans)); t = new tree; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%lld %lld %lld", X + i, Y + i, R + i); ord[i] = i; pdd rotated = rotate(X[i], Y[i]); a[i] = {rotated, i}; } sort(ord, ord + n, [&](int x, int y){ if(R[x] != R[y]) { return R[x] > R[y]; } return x < y; }); init(t, 0, n - 1); for(int i = 0; i < n; i++) { int curr = ord[i]; if(ans[curr] != -1) { continue; } ans[curr] = curr; calculate(X[curr], Y[curr], R[curr], curr); } for(int i = 0; i < n; i++) { printf("%d ", ans[i] + 1); } puts(""); return 0; }

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
circle_selection.cpp:159:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |     scanf("%lld %lld %lld", X + i, Y + i, R + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~