考前挣扎
KD树好题！
暴力模拟 通过kd树的结构把子树内的圈圈框起来
然后排个序根据圆心距 <= R1+R2来判断是否有交点
然后随便转个角度就可以保持优越的nlgn啦
卡精度差评 必须写eps差评
//Love and Freedom.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define db long double
#define inf 20021225
#define ll long long
#define mxn 310000
#define eps 1e-3
using namespace std;
struct poi
{
db x,y;
poi(){}
poi(db _x,db _y){x=_x,y=_y;}
};
struct circle
{
db r; poi pos; int id;
circle(){}
circle(poi _pos,db _r){pos=_pos;r = _r;}
}cc[mxn];
int ans[mxn];
struct node
{
int son[2],id; //poi p;
db r,mr,mx[2],mn[2],pos[2];
};
bool flag;
bool cmp(circle a,circle b)
{
if(flag?abs(a.pos.x - b.pos.x)<eps:abs(a.pos.y-b.pos.y)<eps) return a.r>b.r;
return flag?a.pos.x<b.pos.x:a.pos.y<b.pos.y;
}
db dis(poi a,poi b)
{
return (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y);
}
struct KD
{
node t[mxn]; int rt;
void update(int x)
{
int l = t[x].son[0];
int r = t[x].son[1];
for(int c = 0;c < 2; c++)
{
if(l) t[x].mx[c]=max(t[l].mx[c],t[x].mx[c]),t[x].mn[c]=min(t[l].mn[c],t[x].mn[c]);
if(r) t[x].mx[c]=max(t[r].mx[c],t[x].mx[c]),t[x].mn[c]=min(t[r].mn[c],t[x].mn[c]);
}
if(l) t[x].mr=max(t[x].mr,t[l].mr);
if(r) t[x].mr=max(t[x].mr,t[r].mr);
}
void build(int &x,int l,int r,bool w)
{
flag = w; sort(cc+l,cc+r+1,cmp);
int mid = l+r>>1; x = mid;
t[x].mr = t[x].r = cc[mid].r; t[x].id = cc[mid].id;
for(int c = 0;c < 2;c++)
t[x].pos[c] = t[x].mn[c] = t[x].mx[c] = c?cc[mid].pos.y:cc[mid].pos.x;
if(l<mid) build(t[x].son[0],l,mid-1,w^1);
if(mid<r) build(t[x].son[1],mid+1,r,w^1);
update(x);
}
bool del(circle goal, circle tmp)
{
if(dis(goal.pos,tmp.pos) - (goal.r+tmp.r)*(goal.r+tmp.r)<=eps) return true;
return false;
}
db check(int x,circle goal)
{
db ans = 0;
for(int c = 0;c < 2;c++)
{
db wz = (c?goal.pos.y:goal.pos.x),tmp;
if(wz>=t[x].mn[c] && wz<=t[x].mx[c]) tmp = 0;
else tmp = min(abs(t[x].mn[c]-wz),abs(t[x].mx[c]-wz));
ans += tmp*tmp;
}
return ans;
}
void query(int x,circle goal,int w)
{
if(!ans[t[x].id] && del(goal,circle(poi(t[x].pos[0],t[x].pos[1]),t[x].r))) ans[t[x].id] = w;
int l = t[x].son[0], r = t[x].son[1]; db d1,d2;
if(l)
{
d1 = check(l,goal);
if((t[l].mr+goal.r)*(t[l].mr+goal.r) -d1>= -eps) query(l,goal,w);
}
if(r)
{
d2 = check(r,goal);
if((t[r].mr+goal.r)*(t[r].mr+goal.r) -d2>= -eps) query(r,goal,w);
}
}
}kd;
bool qaq(circle a,circle b)
{
return abs(a.r-b.r)<eps?a.id<b.id:a.r>b.r;
}
const db phi = 1.05426;
poi rotate(poi a)
{
return poi(cosl(phi)*a.x-sinl(phi)*a.y,sinl(phi)*a.x+cosl(phi)*a.y);
}
int main()
{
int n; scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%Lf%Lf%Lf",&cc[i].pos.x,&cc[i].pos.y,&cc[i].r),cc[i].id=i;
cc[i].pos = rotate(cc[i].pos);
}
kd.build(kd.rt,1,n,0);
sort(cc+1,cc+n+1,qaq);
for(int i=1;i<=n;i++)
if(!ans[cc[i].id])
kd.query(kd.rt,cc[i],cc[i].id);
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}