1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 300005;
const double sina=sqrt(2)/2, cosa=sina, eps=1e-3;
int n, D, now, root, ans[N], b[N], f[N], ch[N][2];
double mn[N][2], mx[N][2];
bool del[N];
struct circle{
int r, id;
double s[2];
inline bool operator <(const circle &rhs)const{ return r>rhs.r;}
}anow, a[N];
inline void update(int t){
mn[t][0]=a[t].s[0]-a[t].r, mn[t][1]=a[t].s[1]-a[t].r;
mx[t][0]=a[t].s[0]+a[t].r, mx[t][1]=a[t].s[1]+a[t].r;
for(int i=0; i<2; ++i) if(ch[t][i]) for(int j=0; j<2; ++j)
mx[t][j]=max(mx[t][j], mx[ch[t][i]][j]),
mn[t][j]=min(mn[t][j], mn[ch[t][i]][j]);
}
inline bool cmp(const circle &x, const circle &y){ return x.s[D]<y.s[D];}
void build(int &t, int l, int r, int k){
if(l>r) return;
int mid=l+r>>1;
t=mid, D=k, nth_element(a+l, a+mid, a+r+1, cmp);
build(ch[t][0], l, mid-1, k^1), build(ch[t][1], mid+1, r, k^1), update(t);
}
inline double sqr(double x){ return x*x;}
void erase(int t, int k){
if(!t || anow.s[0]-anow.r>mx[t][0] || anow.s[1]-anow.r>mx[t][1] ||
anow.s[0]+anow.r<mn[t][0] || anow.s[1]+anow.r<mn[t][1]) return;
if(!del[t])
if(sqr(a[t].s[0]-anow.s[0])+sqr(a[t].s[1]-anow.s[1])<=sqr(a[t].r+anow.r)+eps)
del[t]=1, ans[a[t].id]=anow.id, a[t].s[0]=a[t].s[1]=0, a[t].r=-2e9;
erase(ch[t][0], k^1), erase(ch[t][1], k^1), update(t);
}
int main() {
read(n);
for(int i=1; i<=n; ++i){
int x, y;
read(x), read(y), read(a[i].r), a[i].id=i;
a[i].s[0]=x*cosa-y*sina, a[i].s[1]=x*sina+y*cosa;
}
stable_sort(a+1, a+n+1);
for(int i=1; i<=n; ++i) b[a[i].id]=i;
build(root, 1, n, 0);
for(int i=1; i<=n; ++i) f[b[a[i].id]]=i;
for(int i=1; i<=n; ++i) if(!del[now=f[i]]) anow=a[now], erase(root, 0);
for(int i=1; i<=n; ++i) print(ans[i]), print(' ');
return flush(), 0;
}
|