Description

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： 对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。 例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

Input

第一行包含两个整数N和K(1< = N < = 1000,1< K < = N)，分别代表了野人居住点的数量和部落的数量。

接下来N行，每行包含两个正整数x,y，描述了一个居住点的坐标(0 < =x, y < =10000)

Output

输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

Sample Input

4 20 00 11 11 0

Sample Output

1.00

Solution

有点像Kruskal

首先\(n^2\)对点两两建边，边权就是距离

然后二分答案，二分出最大的最小距离\(ans\)

对于两个点，如果它的距离小于\(ans\)，那么它们一定在同一个集合中。如果最终划分出的集合数量小于\(k\)则为非法情况

如果划分出的集合数量大于\(k\)，那么我们可以随意合并若干个不同的集合使得数量回到\(k\)，而不会对答案产生影响

Code

怕有精度误差，所以我在输出时才对距离开方

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 1005using namespace std;typedef long long ll;template 
          
           inline void read(T &t){ t=0;char c=getchar();int f=0; while(!isdigit(c)){f|=c=='-';c=getchar();} while(isdigit(c)){t=t*10+c-'0';c=getchar();} if(f)t=-t;}const double eps=1e-4;int n,K;double x[maxn],y[maxn];int prt[maxn];int ecnt;struct edge{ int u,v; double w; edge(int x=0,int y=0,double z=0) { u=x,v=y,w=z; };}g[maxn*maxn/2];double dist(const int &a,const int &b){ return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);}bool cmp(const edge &a,const edge &b){ return a.w
           
            eps) { double mid=(l+r)/2; if(Check(mid)) l=mid; else r=mid; } printf("%.2f",sqrt(l)); return 0;}