一道最小生成树经典题
由于是最靠近的两个部落尽可能远，如果我们先处理出任意两个居住点之间的距离并将其当做边，那么我们可以发现，因为在一个部落里面的边是不用计入答案的，所以应该要尽量把小边放在一个部落里，
由此，我们可以想到最小生成树，也是每次都优先选小的边，只不过这里要求的是尽可能远，所以就相当于是把选出的最小边都去掉。
那k个集合的问题怎么办呢？
我们在做最小生成树的时候，其实也是集合不断合并的过程，放在这道题中，就相当于是一个个居住点不断被划分到部落里的过程，因此当集合只剩k个时，也就是分配好了k个部落，因为每次合并都会少一个集合，所以我们用一个变量记录下来当前还有多少集合（或还要删几个，已经删了几个之类的都可以）。
剩k个的时候就退出。
然后由于边已经排好序，所以我们从退出的那条边（没有被选上）开始，依次向后遍历，第一个不在一个集合里的边就是答案（因为在一个集合里就意味这被划分到了一个部落，不能算作答案）
简而言之就是：将求最小值最大转换为用kruskal去掉小边，最后就会留下最优的边
#include<bits/stdc++.h>
using namespace std;
#define AC 1000010
#define R register int
struct abc{
int f,w,length;
}way[AC];
int n,k,x[],y[],now;
int father[],tot,cnt;//tot为已经消除的并查集个数， bool cmp(abc a,abc b)
{
return a.length<b.length;
} inline int find(int x)
{
if(father[x]==x) return x;
else return father[x]=find(father[x]);
} inline int read()
{
int x=;char c;
while(isspace(c=getchar()));
while(c>='' && c<='')x=x*+c-'',c=getchar();
return x;
} void kruskal()
{
int father1,father2;
for(R i=;i<=cnt;i++)
{
father1=find(way[i].f),father2=find(way[i].w);
if(father1!=father2)
{
tot++;
if(father1<father2) father[father2]=father1;
else father[father1]=father2;
if(n-tot==k)//合并到k个集合就退出
{
now=i+;//搜索答案从now开始，因为之前没有选的边都是因为在同一个集合内
break;//而这里要统计的是不同部落的距离
}
}
}
} void pre()
{
n=read(),k=read();
for(R i=;i<=n;i++) x[i]=read(),y[i]=read(),father[i]=i;
for(R i=;i<=n;i++)
for(R j=i+;j<=n;j++)
{
way[++cnt].f=i,way[cnt].w=j;
way[cnt].length=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}//非真实距离
sort(way+,way+cnt+,cmp);
} void work()
{
kruskal();
for(R i=now;i<=cnt;i++)
{
if(find(way[i].f) != find(way[i].w))
{
printf("%.2f\n",sqrt((double)way[i].length));
exit();
}
}
} int main()
{
// freopen("in.in","r",stdin);
pre();
work();
// fclose(stdin);
return ;
}