问题 3322 --蚂蚁群

3322: 蚂蚁群

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

在一张地图中(可以看成平面直角坐标系），住着n只蚂蚁。蚂蚁是群居动物，你现在的任务是把这n只蚂蚁分成k个群，我们把两个蚂蚁群的距离，定义为群中距离最近的那两只蚂蚁居住点的距离。对于任意一种蚂蚁群划分的方法，都能够求出两个群之间的距离，你希望求出一种蚂蚁划分的方法，使靠得最近的两个部落尽可能远离。

输入

输入文件第一行包含两个整数 n 和 k，分别代表了蚂蚁居住点的数量和群的数量。

接下来 n 行，每行包含两个整数 x，y，描述了一个居住点的坐标。

输出

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

样例输入

样例1
4 2
0 0
0 1
1 1
1 0
样例2
9 3
2 2
2 3
3 2
3 3
3 5
3 6
4 6
6 2
6 3

样例输出

样例1
1.00
样例2
2.00

提示

对于100%的数据，保证:2<=k<=1000,0<=x,y<=10^4

来源

二分、并查集、最小生成树 

[提交][状态]