题面
https://www.luogu.org/problem/P4631
题解
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=300050; int now,n,root,ans[N]; struct dat { int d[2],r,id; bool operator < (const dat &rhs) const { return d[now]<rhs.d[now]; } } a[N]; struct node { dat a; int ch[2],mn[2],mx[2]; } t[N]; void cmax(int &x,int y){x=max(x,y);} void cmin(int &x,int y){x=min(x,y);} bool cmp(dat x,dat y){ return x.r>y.r || x.r==y.r && x.id<y.id;} long long sqr(long long x) {return x*x;} struct kd_tree { void update(int x,int y) { cmin(t[x].mn[0],t[y].mn[0]); cmax(t[x].mx[0],t[y].mx[0]); cmin(t[x].mn[1],t[y].mn[1]); cmax(t[x].mx[1],t[y].mx[1]); } void pushup(int k) { int x=t[k].a.d[0],y=t[k].a.d[1],r=t[k].a.r; t[k].mn[0]=x-r; t[k].mx[0]=x+r; t[k].mn[1]=y-r; t[k].mx[1]=y+r; if (t[k].ch[0]) update(k,t[k].ch[0]); if (t[k].ch[1]) update(k,t[k].ch[1]); } void build(int &k,int l,int r,int tag) { int mid=(l+r)>>1;now=tag; nth_element(a+l,a+mid,a+r+1); k=mid; t[k].a=a[mid]; if (l<mid) build(t[k].ch[0],l,mid-1,tag^1); else t[k].ch[0]=0; if (mid<r) build(t[k].ch[1],mid+1,r,tag^1); else t[k].ch[1]=0; pushup(k); } bool check(int k,dat A) { int x=A.d[0],y=A.d[1],r=A.r+t[k].a.r,xx=t[k].a.d[0],yy=t[k].a.d[1]; return sqr(1LL*x-xx)+sqr(1LL*y-yy)<=sqr(r); } bool far(int k,dat A) { int x=A.d[0],y=A.d[1],r=A.r; if (x+r<t[k].mn[0] || y+r<t[k].mn[1] || x-r>t[k].mx[0] || y-r>t[k].mx[1]) return 1; return 0; } void query(int k,dat A) { if (far(k,A)) return; if (!ans[t[k].a.id] && check(k,A)) ans[t[k].a.id]=A.id; if (t[k].ch[0]) query(t[k].ch[0],A); if (t[k].ch[1]) query(t[k].ch[1],A); } } kd; int main(){ int i; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d %d %d",&a[i].d[0],&a[i].d[1],&a[i].r); a[i].id=i; } kd.build(root,1,n,0); sort(a+1,a+n+1,cmp); for (i=1;i<=n;i++) if (!ans[a[i].id]) kd.query(root,a[i]); for (i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }