P4047 [JSOI2010]部落划分

显然二分答案(mid)，然后距离(leq mid)的点对只能放在一个部落里。然后可以并查集(O(n^2))算出有多少个部落。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,k,x[1010],y[1010],fa[1010],siz[1010];
il int hd(int x){return fa[x]==x?x:fa[x]=hd(fa[x]);}
il vd Union(int x,int y){
    x=hd(x),y=hd(y);
    if(x==y)return;
    if(siz[x]<siz[y])fa[x]=y,siz[y]+=siz[x];
    else fa[y]=x,siz[x]+=siz[y];
}
il int check(double mid){
    mid*=mid;
    for(int i=1;i<=n;++i)fa[i]=i,siz[i]=1;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<mid)
                Union(i,j);
    int tot=0;
    for(int i=1;i<=n;++i)if(fa[i]==i)++tot;
    return tot;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("4047.in","r",stdin);
    freopen("4047.out","w",stdout);
#endif
    n=gi(),k=gi();
    for(int i=1;i<=n;++i)x[i]=gi(),y[i]=gi();
    double l=0,r=14143,mid;
    while(r-l>1e-4){
        mid=(l+r)*0.5;
        if(check(mid)<=k)r=mid;
        else l=mid;
    }
    r=14143;
    while(r-l>1e-4){
        mid=(l+r)*0.5;
        if(check(mid)<k)r=mid;
        else l=mid;
    }
    printf("%.2lf
",l);
    return 0;
}