传送门

那个当前半径最大的圆可以用堆维护.这道题一个想法就是优化找和当前圆有交的圆的过程.考虑对于所有圆心建KD-tree,然后在树上遍历的找这样的点.只要某个点子树内的点构成的矩形区域到当前圆心的最近距离\(>2\)倍半径就不用找了

然而在loj上过不去,这时就可以用一个很鸡贼的优化,对于所有点绕原点旋转一定角度,然后就跑的过了(可能是全在一条直线上建KD-tree会出锅(雾)).稍微注意精度误差就行了

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define db double

using namespace std;

const int N=3e5+10;

const LL inf=1ll<<61;

const db eps=1e-3,tpd=sqrt(2)/2;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int nd;

struct point

{

	db d[2];

	int i;

	bool operator < (const point &bb) const {return fabs(d[nd]-bb.d[nd])>eps?d[nd]<bb.d[nd]:i<bb.i;}

}a[N],b[N],qwq;

struct cir

{

	point p;

	db r;

	bool operator < (const cir &bb) const {return fabs(r-bb.r)>eps?r<bb.r:p.i>bb.p.i;}

}c[N];

priority_queue<cir> hp;

int n,m,rt,ch[N][2],an[N],ii;

db mx[N][2],my[N][2];

void bui(int &o,int l,int r,int nnd)

{

	if(l>r) return;

	if(l==r)

	{

		o=b[l].i;

		mx[o][0]=mx[o][1]=a[o].d[0];

		my[o][0]=my[o][1]=a[o].d[1];

		return;

	}

	int mid=(l+r)>>1;

	nd=nnd;

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

	o=b[mid].i;

	mx[o][0]=mx[o][1]=a[o].d[0];

	my[o][0]=my[o][1]=a[o].d[1];

	bui(ch[o][0],l,mid-1,nnd^1);

	bui(ch[o][1],mid+1,r,nnd^1);

	mx[o][0]=min(mx[o][0],min(mx[ch[o][0]][0],mx[ch[o][1]][0]));

	mx[o][1]=max(mx[o][1],max(mx[ch[o][0]][1],mx[ch[o][1]][1]));

	my[o][0]=min(my[o][0],min(my[ch[o][0]][0],my[ch[o][1]][0]));

	my[o][1]=max(my[o][1],max(my[ch[o][0]][1],my[ch[o][1]][1]));

}

db dis(point aa,point bb){return (aa.d[0]-bb.d[0])*(aa.d[0]-bb.d[0])+(aa.d[1]-bb.d[1])*(aa.d[1]-bb.d[1]);}

db expt(int o)

{

	if(!o) return inf;

	db xx=min(mx[o][1]-qwq.d[0],qwq.d[0]-mx[o][0])<-eps?min(fabs(mx[o][1]-qwq.d[0]),fabs(qwq.d[0]-mx[o][0])):0;

	db yy=min(my[o][1]-qwq.d[1],qwq.d[1]-my[o][0])<-eps?min(fabs(my[o][1]-qwq.d[1]),fabs(qwq.d[1]-my[o][0])):0;

	return xx*xx+yy*yy;

}

void wk(int o)

{

	if(!o||expt(o)>(db)qwq.i*(db)qwq.i+eps) return;

	if(!an[o])

	{

		db rr=(db)qwq.i/2+c[o].r;

		if(dis(a[o],qwq)<rr*rr+eps) an[o]=ii;

	}

	wk(ch[o][0]),wk(ch[o][1]);

}

int main()

{

	n=rd();

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

	{

		db xx=rd(),yy=rd();

		a[i].d[0]=tpd*xx+tpd*yy,a[i].d[1]=tpd*yy-tpd*xx;

		a[i].i=i;

		b[i]=a[i];

		c[i].p=a[i],c[i].r=rd();

		hp.push(c[i]);

	}

	mx[0][0]=my[0][0]=inf,mx[0][1]=my[0][1]=-inf;

	bui(rt,1,n,0);

	while("ji ni tai mei")

	{

		while(!hp.empty()&&an[hp.top().p.i]) hp.pop();

		if(hp.empty()) break;

		cir cc=hp.top();

		hp.pop();

		ii=cc.p.i;

		qwq=cc.p,qwq.i=cc.r*2;

		wk(rt);

	}

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

    return 0;

}