那个当前半径最大的圆可以用堆维护.这道题一个想法就是优化找和当前圆有交的圆的过程.考虑对于所有圆心建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;
}