北极的某区域共有 nn 座村庄，每座村庄的坐标用一对整数 (x,y)(x,y) 表示。

为了加强联系，决定在村庄之间建立通讯网络，使每两座村庄之间都可以直接或间接通讯。

通讯工具可以是无线电收发机，也可以是卫星设备。

无线电收发机有多种不同型号，不同型号的无线电收发机有一个不同的参数 dd，两座村庄之间的距离如果不超过 dd，就可以用该型号的无线电收发机直接通讯，dd 值越大的型号价格越贵。现在要先选择某一种型号的无线电收发机，然后t统一给所有村庄配备，数量不限，但型号都是 相同的。

配备卫星设备的两座村庄无论相距多远都可以直接通讯，但卫星设备是 有限的，只能给一部分村庄配备。

现在有 kk 台卫星设备，请你编一个程序，计算出应该如何分配这 kk 台卫星设备，才能使所配备的无线电收发机的 dd 值最小。

例如，对于下面三座村庄：

1.png

其中，|AB|=10,|BC|=20,|AC|=105√≈22.36|AB|=10,|BC|=20,|AC|=105≈22.36。

如果没有任何卫星设备或只有 11 台卫星设备 (k=0k=0 或 k=1k=1)，则满足条件的最小的 d=20d=20，因为 AA 和 BB，BB 和 CC 可以用无线电直接通讯；而 AA 和 CC 可以用 BB 中转实现间接通讯 (即消息从 AA 传到 BB，再从 BB 传到 CC)；

如果有 22 台卫星设备 (k=2k=2)，则可以把这两台设备分别分配给 BB 和 CC ，这样最小的 dd 可取 1010，因为 AA 和 BB 之间可以用无线电直接通讯；BB 和 CC 之间可以用卫星直接通讯；AA 和 CC 可以用 BB 中转实现间接通讯。

如果有 33 台卫星设备，则 A,B,CA,B,C 两两之间都可以直接用卫星通讯，最小的 dd 可取 00。

输入格式
第一行为由空格隔开的两个整数 n,kn,k;

接下来 nn 行，每行两个整数，第 ii 行的 xi,yixi,yi 表示第 ii 座村庄的坐标 (xi,yixi,yi)。

输出格式
一个实数，表示最小的 dd 值，结果保留 22 位小数。

数据范围
1≤n≤5001≤n≤500,
0≤x,y≤1040≤x,y≤104,
0≤k≤1000≤k≤100
输入样例：
3 2
10 10
10 0
30 0
输出样例：
10.00

分析:
一看到联通块,我们可以快速的想到克鲁斯卡尔算法.
回忆克鲁斯卡尔算法的过程:
1.将边权从小到大排序.
2.依次从小到大扫描每一条边,合并没有合并的点集.

我们发现第二步本质上就是在维护联通快的个数.
由此我们就得到了这道题的解决方法:
正常执行克鲁斯卡尔算法,记录当前已经加入了几条边.
当加入某条边后,恰好加入了n-k条边.
那么这条边的权值就是最终答案.

#include <bits/stdc++.h>

using namespace std;

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

int n,m,k;
struct Edge
{
    int a, b;
    double w;
    bool operator< (const Edge &t)const
    {
        return w < t.w;
    }
}e[M];
int p[N];
double a[N],b[N];
double count(double x1,double y1,double x2,double y2){
    int x=(x1-x2)*(x1-x2);
    int y=(y1-y2)*(y1-y2);
    return sqrt(1.0*(x+y));
}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >>k;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i]>> b[i];
    }
    for (int i = 1; i <= n; i ++ ){
        for (int j = i+1; j <= n; j ++ ){
          double w=count(a[i],b[i],a[j],b[j]);
             e[m++] = {i, j, w};
        }
    }
    sort(e, e + m);

    int cnt = n;
    double res;
    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;
            res=w;
            cnt--;
        }
    }
    printf("%.2f",res);
    return 0;
}