考前挣扎

KD树好题！

暴力模拟 通过kd树的结构把子树内的圈圈框起来

然后排个序根据圆心距 <= R1+R2来判断是否有交点

然后随便转个角度就可以保持优越的nlgn啦

卡精度差评 必须写eps差评

//Love and Freedom.#include
    
     #include
     
      #include
      
       #include
       
        #define db long double#define inf 20021225#define ll long long#define mxn 310000#define eps 1e-3using 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)
        
         
          b.r; return flag?a.pos.x
          
           
            < 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
            
             < 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)
             
              
               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;}