莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 一棵最小生成树，最大的 k 条边都用卫星设备，d 就是剩下 n - 1 - k 条边的最大值
2. 假设一开始有 n 个卫星设备，那么最小的 d 就是 0，每减少 1 个卫星设备，d 就会被更新
3. 按照 Kruskal 算法的顺序，当卫星设备减少至 k 时，当前 d 就是答案

可参考： Kruskal算法求最小生成树

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 510, M = N * N / 2;

int n,m,k;
PII q[N];
struct Edge
{
    int a,b;
    double w;
    bool operator< (const Edge &t) const
    {
        return w<t.w;
    }
}e[M];
int p[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

//计算两点之间的直线距离
double get_dist(PII a,PII b)
{
    int dx=a.x-b.x,dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;

    //不要有重复边
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            e[m++]={i,j,get_dist(q[i],q[j])};

    //按边的大小排序
    sort(e,e+m);

    for(int i=1;i<=n;i++) p[i]=i;

    int cnt=n; //卫星个数
    double res=0; //满足条件的最小的d
    for(int i=0;i<m;i++)
    {
        if(cnt<=k) break;

        int a=find(e[i].a),b=find(e[i].b);
        double w=e[i].w;
        if(a!=b)
        {
            p[a]=b;
            cnt--;
            res=w;
        }
    }

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

    return 0;
}