二分法

花了半天时间写了个二分，但写完后感觉DFS或者BFS也能求连通块来着，用并查集似乎有点多余
写完后看y总视频才发现二分确实是一个憨憨做法，但就权当开拓一下思路了

//本题目的关键在于理解：一个卫星意味着一个连通块。
//有k个卫星意味着删去一些边后，只要剩下的连通块的数目<=k,整张图仍然可以连通
//（或许可以通过二分求解）
//问题转换为：求一个最小值d，使得将>d的边都删除之后，剩余的连通块的个数<=k

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=N*N+N;
const double eps=1e-4;
typedef pair<int,int> PII;
#define x first
#define y second

int n,k;
//并查集
int p[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//建边
struct Edge{
    int a,b;
    double w;
    bool operator <(Edge b){
        return w<b.w;
    }
}e[M];
int cnt;

vector<PII> point;
//计算点a,b之间的欧式距离
double get_dist(PII a,PII b){
    double dx=a.x-b.x,dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
//计算[0,sz)区间内部的边所能形成的连通块的数量，如果<=k则check返回true
int kruskal(double bound,int sz){
    for(int i=0;i<n;i++) p[i]=i;
    int num=0;
    for(int i=0;i<sz;i++){
        int a=e[i].a,b=e[i].b,w=e[i].w;
        if(find(a)!=find(b)){
            num++;
            p[find(a)]=find(b); 
        }

    }
    return n-num;//返回连通块的数目
}

bool check(double bound){
    //[0,sz)就是<=bound的边所在的区间
    int sz=0;
    for(int i=0;i<cnt;i++){
        if(e[i].w>bound){
            sz=i;
            break;
        }
    }
    int ans=kruskal(bound,sz);//kruskal输入一个区间，输出区间内连通块的个数
    return ans<=k;
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        point.push_back({x,y});
    }
    //开始建图，连边
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            PII a=point[i],b=point[j];
            double w=get_dist(a,b);
            e[cnt++]={i,j,w};
        }
    }

    //将边排序，便于使用kruskal算法
    sort(e,e+cnt);

    //二分答案
    double l=0,r=e[cnt-1].w;

    while(r-l>1e-6){
        double mi=(l+r)/2;
        //check是检查当前的mi是否满足选择的所有d>mi，对所有<mi的边kruskal之后，形成的连通块数目<=k。
        if(check(mi)) r=mi;//<=k，则d可以扩大一些
        else l=mi;//否则减小一些
    }

    printf("%.2lf\n",r);
}