我不知道题解应该叫什么名字

· · 题解

题目要求：每次选择 r 最大的，找到和其有交集的部分，将其删除，以此类推。

选择 r 最大的这一步，可以考虑将原数组按照 r 排序，按照大小顺序扫过去，如果没有被删除，用当前点删除。

那么我们要实现的就只是求交集了。

求交集，考虑使用 K-D Tree。

两个圆有交，需要满足 dis(i,j) \le r_i+r_j，其中 dis(i,j) 是 i 和 j 圆心的距离。

考虑在 K-D Tree 中维护对应的 \min_x,\max_x,\min_y,\max_y,\max_r。

因为这里要记录答案，所以完全包含这种情况也需要向下找。

直接写一遍，你发现这道题卡了 K-D Tree，但不多，提交记录。

实际上这里是我写的不好看，写好看一点应该不旋转也是可以过的。

我们考虑使用随机旋转坐标系来处理对应的 hack。

我们将平面随机旋转一个角度 \theta，这样的话，原本的 (x,y) 就会变成(x \cos \theta-y \sin \theta, x \sin \theta+y \cos \theta)。

记得给 x,y,\max_x,\min_x,\max_y,\min_y 开 long double，并开一个 10^{-6} 的 eps。

:::success[代码]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mid ((l+r)>>1)
using namespace std;

const int N=3e5+5;const ld Sin=0.342020143325668733044099614,Cos=0.939692620785908384054109277,eps=1e-6;
int tmp[N],ans[N];struct edge{ld x,y;int ox,oy,r,id;}a[N];
struct node{ld x,y,maxx,minx,maxy,miny;int ox,oy,r,maxr,ls,rs,sum,now;}tr[N];
/*now 记录当前点是否找到了答案，从而统计当前子树是否全部处理完毕*/

inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*f;
}

inline bool cmp1(int x,int y){return tr[x].x<tr[y].x;}

inline bool cmp2(int x,int y){return tr[x].y<tr[y].y;}

inline bool operator < (edge x,edge y){
    if(x.r!=y.r) return x.r>y.r;
    return x.id<y.id;
}

inline void pushup(int x){//处理 minx,maxx,miny,maxy,maxr 等信息，给 sum 一个初始值防止直接结束
    tr[x].maxr=tr[x].r;
    tr[x].sum=tr[x].now;
    tr[x].maxx=tr[x].minx=tr[x].x;
    tr[x].maxy=tr[x].miny=tr[x].y;
    if(tr[x].ls){
        tr[x].sum+=tr[tr[x].ls].sum;
        tr[x].maxr=max(tr[x].maxr,tr[tr[x].ls].maxr);
        tr[x].minx=min(tr[x].minx,tr[tr[x].ls].minx);
        tr[x].maxx=max(tr[x].maxx,tr[tr[x].ls].maxx);
        tr[x].miny=min(tr[x].miny,tr[tr[x].ls].miny);
        tr[x].maxy=max(tr[x].maxy,tr[tr[x].ls].maxy);
    }
    if(tr[x].rs){
        tr[x].sum+=tr[tr[x].rs].sum;
        tr[x].maxr=max(tr[x].maxr,tr[tr[x].rs].maxr);
        tr[x].minx=min(tr[x].minx,tr[tr[x].rs].minx);
        tr[x].maxx=max(tr[x].maxx,tr[tr[x].rs].maxx);
        tr[x].miny=min(tr[x].miny,tr[tr[x].rs].miny);
        tr[x].maxy=max(tr[x].maxy,tr[tr[x].rs].maxy);
    }
}

inline void push(int x){//更新有多少点还没有答案
    tr[x].sum=tr[x].now;
    if(tr[x].ls) tr[x].sum+=tr[tr[x].ls].sum;
    if(tr[x].rs) tr[x].sum+=tr[tr[x].rs].sum;
}

inline int build(int l,int r,int op){
    if(op==0) nth_element(tmp+l,tmp+mid,tmp+r+1,cmp1);
    else nth_element(tmp+l,tmp+mid,tmp+r+1,cmp2);
    int x=tmp[mid];
    if(l<=mid-1) tr[x].ls=build(l,mid-1,op^1);
    if(mid+1<=r) tr[x].rs=build(mid+1,r,op^1);
    pushup(x);return x;
}

inline void solve(int x,ld tx,ld ty,int ox,int oy,int r,int i){
    if(!x) return;
    ld disx=((tr[x].minx-eps<=tx && tx<=tr[x].maxx+eps)?0:min((tr[x].maxx-tx)*(tr[x].maxx-tx),(tr[x].minx-tx)*(tr[x].minx-tx)));//横坐标上的距离的平方，如果在中间就当成没有，不在中间就取和两侧的最小距离
    ld disy=((tr[x].miny-eps<=ty && ty<=tr[x].maxy+eps)?0:min((tr[x].maxy-ty)*(tr[x].maxy-ty),(tr[x].miny-ty)*(tr[x].miny-ty)));//纵坐标上的距离的平方，如果在中间就当成没有，不在中间就取和两侧的最小距离
    if(disx+disy>eps+1ll*(r+tr[x].maxr)*(r+tr[x].maxr) || tr[x].sum==0) return;//横纵坐标距离平方和 > 半径之和的平方，一定不可能有交 || 每一个节点都已经有答案
    //推荐一个个人觉得很不错的写法，我们只在剪枝的时候使用随机旋转的值，比较当前点的时候使用原本的值，这样就不需要太担心浮点误差
    if(ans[x]==0 && 1ll*(tr[x].ox-ox)*(tr[x].ox-ox)+1ll*(tr[x].oy-oy)*(tr[x].oy-oy)<=1ll*(r+tr[x].r)*(r+tr[x].r)) tr[x].now=0,ans[x]=i;//当前点有交，记录答案
    solve(tr[x].ls,tx,ty,ox,oy,r,i);solve(tr[x].rs,tx,ty,ox,oy,r,i);push(x);//向两侧递归，更新当前子树有多少点还没有答案
}

signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x=read(),y=read(),r=read();tmp[i]=i;tr[i].r=r;tr[i].now=1;tr[i].ox=x,tr[i].oy=y;
        tr[i].x=x*Cos-y*Sin,tr[i].y=x*Sin+y*Cos;a[i]={tr[i].x,tr[i].y,x,y,r,i};//记录随机旋转后的值
    }
    int root=build(1,n,0);
    sort(a+1,a+n+1);//排序实现先选大的再选小的
    for(int i=1;i<=n;i++){//注意一下这里枚举的是编号，所以后面要用 a[i].id
        if(ans[a[i].id]) continue;//已经有答案了
        solve(root,a[i].x,a[i].y,a[i].ox,a[i].oy,a[i].r,a[i].id);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}

:::

本人写代码的时候因为调疯了，重构了好几次，注释比较多，自认为可读性较高。