Description

给出 \(n\) 个圆 \((x_i,y_i,r_i)\)

每次重复以下步骤:

找出半径最大的圆,并删除与这个圆相交的圆

求出每一个圆是被哪个圆删除的

Solution

\(kd-tree\) 搞一下

维护能够围住所有圆的最小矩形

然后模拟题意,枚举半径最大的圆

查询时就判断询问的圆是否与这个矩形有交,有交就递归下去

#include<bits/stdc++.h>

#define sqr(x) ((x)*(x))

using namespace std;

template<class T>void gi(T &x){

	int f;char c;

	for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

	for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;

}

const int N=3e5+10,inf=2e9+10;const double eps=1e-7;

int n,rt,D,ans[N];

struct data{

	double a[2],mn[2],mx[2],R;int l,r,tag,id;

	inline double& operator [](int x){return a[x];}

}t[N],c[N],W;

inline bool operator <(data p,data q){return p[D]<q[D];}

inline bool comp(data p,data q){return p.R!=q.R?p.R>q.R:p.id<q.id;}

inline void upd(int o){

	int l=t[o].l,r=t[o].r;

	for(int i=0;i<2;i++){

		t[o].mx[i]=-inf;t[o].mn[i]=inf;

		if(!t[o].tag)t[o].mn[i]=min(t[o].mn[i],t[o].a[i]-t[o].R),

							t[o].mx[i]=max(t[o].mx[i],t[o].a[i]+t[o].R);

		if(l)t[o].mn[i]=min(t[o].mn[i],t[l].mn[i]),

				  t[o].mx[i]=max(t[o].mx[i],t[l].mx[i]);

		if(r)t[o].mn[i]=min(t[o].mn[i],t[r].mn[i]),

				  t[o].mx[i]=max(t[o].mx[i],t[r].mx[i]);

	}

}

inline int build(int l,int r,int k){

	int mid=(l+r)>>1,o=mid;D=k;

	nth_element(t+l,t+mid,t+r+1);

	if(l<mid)t[o].l=build(l,mid-1,k^1);

	if(r>mid)t[o].r=build(mid+1,r,k^1);

	return upd(o),o;

}

inline void query(int o){

	if(!o)return ;

	for(int i=0;i<2;i++)

		if(W.a[i]-W.R>t[o].mx[i] || W.a[i]+W.R<t[o].mn[i])return ;

	if(!t[o].tag){

		double dis=0,R=sqr(W.R+t[o].R);

		for(int i=0;i<2;i++)dis+=sqr(t[o].a[i]-W.a[i]);

		if(dis-R<eps)ans[t[o].id]=W.id,t[o].tag=1;

	}

	query(t[o].l);query(t[o].r);

}

int main(){

	freopen("pp.in","r",stdin);

	freopen("pp.out","w",stdout);

	cin>>n;

	double x,y,z;

	for(int i=1;i<=n;i++){

		gi(x);gi(y);gi(z);

		t[i].a[0]=c[i].a[0]=x;t[i].a[1]=c[i].a[1]=y;

		t[i].R=c[i].R=z;c[i].id=t[i].id=i;

	}

	rt=build(1,n,0);

	sort(c+1,c+n+1,comp);

	for(int i=1;i<=n;i++){

		if(ans[c[i].id])continue;

		W=c[i];

		query(rt);

	}

	for(int i=1;i<=n;i++)printf("%d ",ans[i]);

	return 0;

}