题目要求最近的两个部落间距尽可能最远

不难想到一种贪心的方法，对每两个点之间距离从小到大排序，

把每个点看成一个部落

然后不断将距离近的两个部落合并成一个部落，直到剩下了k个部落，那么下一条不同部落之间的边的长度就是答案

显然这个算法是用并查集实现

1 type node=record 2        x,y:longint; 3        w:double; 4      end; 5  6 var a:array[0..500010] of node; 7     fa,d,x,y:array[0..2010] of longint; 8     k,i,j,k1,k2,m,n:longint; 9 10 function getf(x:longint):longint;11   begin12     while fa[x]<>x do x:=fa[x];13     exit(x);14   end;15 16 procedure swap(var a,b:node);17   var c:node;18   begin19     c:=a;20     a:=b;21     b:=c;22   end;23 24 procedure sort(l,r:longint);25   var i,j:longint;26       x:double;27 28   begin29     i:=l;30     j:=r;31     x:=a[(l+r) shr 1].w;32     repeat33       while a[i].w
      
       j) then36       begin37         swap(a[i],a[j]);38         inc(i);39         j:=j-1;40       end;41     until i>j;42     if l
       
        k2 then70     begin71       if d[k1]>d[k2] then fa[k2]:=k172       else begin73         fa[k1]:=k2;74         if d[k1]=d[k2] then inc(d[k2]);75       end;76       dec(j);77     end;78     if j=k-1 then  //剩下k个部落后，下一条【不同】部落之间的边才是答案79     begin80       writeln(a[i].w:0:2);81       break;82     end;83   end;84 end.