5501: 洞穴划分(cave)
Memory Limit:512 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
小杰克对动物很感兴趣,他养了一群蚂蚁来研究他们的习性。小杰克发现,他培养的蚂蚁们虽然是群居,但是,并不是所有蚂蚁都属于一个团体,蚂蚁们会形成自己的小团体,不同团体之间会发生冲突。小杰克对这一现象很感兴趣,但是他不知道团体是如何分布的。
小杰克根据培养地势的特征,绘制了一份地图。地图上标注了 n 只蚂蚁的洞穴。同一个团体的成员的洞穴是相邻的。小杰克认为两个团体之间的距离等于这两个团体中距离最近的两个洞穴的距离。
小杰克还发现:这些蚂蚁一共分为 k 个团体。小杰克想从已有信息中发现更多关于团体的信息,于是他想尝试下列方法:
任何一种团体划分的方法,小杰克都能求出两个团体之间的距离。他希望得出一种团体划分的方式,使离得最近的两个团体的距离尽可能的远。
举个例子,下面的左图是小杰克想要的方式,而右图不是。
这个问题他自己解决不了,请你编程帮助小杰克解决这个问题。
Input
输入文件第一行包含两个整数 n 和 k,分别代表了蚂蚁洞穴的数量和团体的数量。
接下来 n 行,每行包含两个整数 x, y,表示一个洞穴的坐标。
Output
输出一行一个实数,为最好的划分时,最近的两个洞穴的距离,精确到小数点后两位。
Sample Input Copy
9 3
2 2
2 3
3 2
3 3
3 5
3 6
4 6
6 2
6 3
Sample Output Copy
2.00
HINT
对于 100% 的数据,保证 2≤k≤n≤2*10^3,0≤x, y≤10^4。