我们枚举计算点两两之间的距离。

然后我们从小到大考虑每一个距离。

如果我们想让部落之间的最短距离最大,就要尽可能让当前的边连接的两个点在同一个部落中。

因此我们记录剩余的部落数量,每次把最短的,连接两个部落的边连接的两个部落合并成一个,直到剩余部落数量为\(k\)。

然后剩下的边权最小的连接两个部落的边长就是答案了。

就是类似于Kruskal的过程。

code:

#include
    
     using namespace std;const double _=1e-10;struct point{    int x,y;    double operator-(const point&b)const{        return sqrt(1.0*(x-b.x)*(x-b.x)+1.0*(y-b.y)*(y-b.y));    }}p[1010];struct edge{    int u,v;    double w;}e[500010];int n,k,sz,f[1010],tot;bool cmp(edge x,edge y){    return y.w-x.w>_;}int getf(int x){    return f[x]==x?x:f[x]=getf(f[x]);}void Merge(int x,int y){    getf(x),getf(y);    f[f[x]]=f[y];}int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;++i){        scanf("%d%d",&p[i].x,&p[i].y);        for(int j=1;j