/*
A circle (x1, y1, r1) intersects (x2, y2, r2) if and only if
sqrt((x1-x2)^2 + (y1-y2)^2) <= r1+r2
(x1-x2)^2 + (y1-y2)^2 <= (r1+r2)^2
(x1-x2)^2 + (y1-y2)^2 - (r1+r2)^2 <= 0
x1^2 - 2x1x2 + x2^2 + y1^2 - 2y1y2 + y2^2 - r1^2 + 2r1r2 - r2^2 <= 0
(x1^2 + y1^2 - r1^2) + -2x2(x1) - 2y2(y1) + 2r2(r1) + (x2^2 + y2^2 - r2^2) <= 0
Sub 1, brute force
Sub 2
Assume x1 >= x2
(x1-x2)^2 <= (r1+r2)^2
x1-x2 <= r1-r2
r2-x2 <= x1+r1
(Sort by r-x, sweepline by x)
Sub 4, Proof by AC
The condition reduces to finding all points inside a circle (x, y, 2r).
Consider instead the square bounded by ([x-2r, x+2r], [y-2r, y+2r]).
Check every point in the square, then erase all that is in the circle.
Full soln, Proof by AC
Code Sub 4 soln in such a way that it also supports a more general case.
Until 3:40 left, code this
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5+5;
int n;
ll x[MAXN], y[MAXN], r[MAXN];
int ord_r[MAXN];
bool sort_by_r(int a, int b) {
return (r[a] != r[b]) ? (r[a] > r[b]) : (a < b);
}
int ord_xy[MAXN];
bool sort_by_xy(int a, int b) {
if (x[a] != x[b]) return x[a] < x[b];
if (y[a] != y[b]) return y[a] < y[b];
if (r[a] != r[b]) return r[a] > r[b];
return a < b;
}
// Persistent segment tree
namespace pers{
vector<int> tree, lchild, rchild;
int newnode(int val = 0, int lc = -1, int rc = -1) {
tree.push_back(val);
lchild.push_back(lc);
rchild.push_back(rc);
return tree.size()-1;
}
int init(int l = 0, int r = MAXN) {
if (l == r) {
int nn = newnode();
return nn;
}
int mid = (l+r)>>1;
int lc = init(l, mid), rc = init(mid+1, r);
int nn = newnode(0, lc, rc);
return nn;
}
int update(int v, int p, int x, int tl = 0, int tr = MAXN) {
if (tl == tr) {
int nn = newnode(tree[v]+x);
return nn;
}
int mid = (tl+tr)>>1, lc = lchild[v], rc = rchild[v];
if (p <= mid) {
int nn = update(lc, p, x, tl, mid);
lc = nn;
} else {
int nn = update(rc, p, x, mid+1, tr);
rc = nn;
}
int rnn = newnode(tree[lc] + tree[rc], lc, rc);
return rnn;
}
int query(int v, int l, int r, int tl = 0, int tr = MAXN) {
if (l <= tl && tr <= r) return tree[v];
if (r < tl || tr < l) return 0;
int mid = (tl+tr)>>1, lc = lchild[v], rc = rchild[v];
return query(lc, l, r, tl, mid) + query(rc, l, r, mid+1, tr);
}
}
using namespace pers;
int roots[MAXN];
ll xs[MAXN], ys[MAXN];
void generate_coordcompression(ll *a, ll *as) {
for (int i = 1; i <= n; i++) {
as[i] = a[i];
}
as[0] = -2e9;
sort(as, as+n+1);
}
int yid(int y) {
return lower_bound(ys, ys+n+1, y) - ys;
}
int nextpt(int cur, int yl, int yr) {
if (yl > yr) return n+1;
int cs = query(roots[cur], yl, yr);
int l = cur, r = n+1;
while (r-l > 1) {
int mid = (l+r)>>1;
int ms = query(roots[mid], yl, yr);
if (ms > cs) r = mid;
else l = mid;
}
return r;
}
vector<int> getid(int xl, int xr, int yl, int yr) {
xl = lower_bound(xs, xs+n+1, xl) - xs;
xr = upper_bound(xs, xs+n+1, xr) - xs - 1;
yl = lower_bound(ys, ys+n+1, yl) - ys;
yr = upper_bound(ys, ys+n+1, yr) - ys - 1;
int curx = max(0, xl-1);
vector<int> ret;
while (true) {
curx = nextpt(curx, yl, yr);
if (curx > xr) return ret;
ret.push_back(ord_xy[curx]);
}
}
int ans[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i] >> r[i];
}
iota(ord_r+1, ord_r+n+1, 1);
sort(ord_r+1, ord_r+n+1, sort_by_r);
iota(ord_xy+1, ord_xy+n+1, 1);
sort(ord_xy+1, ord_xy+n+1, sort_by_xy);
generate_coordcompression(x, xs);
generate_coordcompression(y, ys);
roots[0] = init();
for (int i = 1; i <= n; i++) {
roots[i] = update(roots[i-1], yid(y[ord_xy[i]]), 1);
}
fill(ans, ans+n+1, -1);
for (int i = 1; i <= n; i++) {
int curc = ord_r[i];
if (ans[curc] != -1) continue;
ans[curc] = curc;
vector<int> id = getid(x[curc] - 2*r[curc], x[curc] + 2*r[curc], y[curc] - 2*r[curc], y[curc] + 2*r[curc]);
for (int j : id) {
if (ans[j] == -1 && (x[curc]-x[j])*(x[curc]-x[j]) + (y[curc]-y[j])*(y[curc]-y[j]) <= (r[curc]+r[j])*(r[curc]+r[j])) {
ans[j] = curc;
}
}
}
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
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
*/
