Description

聪聪研究发现, 荒岛野人总是过着群居的生活, 但是, 并不是整个荒岛上的所有野人都属于同一个部落, 野人们总是拉帮结派形成属于自己的部落, 不同的部落之间则经常发生争斗. 只是, 这一切都成为谜团了----聪聪根本就不知道部落究竟是如何分布的.

不过好消息是, 聪聪得到了一份荒岛的地图. 地图上标注了 \(n\) 个野人居住的地点 (可以看作是平面上的坐标). 我们知道, 同一个部落的野人总是生活在附近. 我们把两个部落的距离, 定义为部落中距离最近的那两个居住点的距离. 聪聪还获得了一个有意义的信息----这些野人总共被分为了 \(k\) 个部落! 这真是个好消息. 聪聪希望从这些信息里挖掘出所有部落的详细信息. 他正在尝试这样一种算法:

对于任意一种部落划分的方法, 都能够求出两个部落之间的距离, 聪聪希望求出一种部落划分的方法, 使靠得最近的两个部落尽可能远离. 例如, 下面的左图表示了一个好的划分, 而右图则不是. 请你编程帮助聪聪解决这个难题.

Input

第一行包含两个整数 \(n\) 和 \(k\), 分别代表了野人居住点的数量和部落的数量.

接下来 \(n\) 行, 每行包含两个正整数 \(x, y\), 描述了一个居住点的坐标 \((0 \leq x, y \leq 10000)\).

Output

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

Sample Input

4 2
0 0
0 1
1 1
1 0

Sample Output

1.00

Data Range

对于所有数据, 满足:\(1 \leq k \leq n \leq 1000\).

Explanation

对于任何一个距离, 不会有一个部落里的两个人距离大于该距离. 这个距离越大, 我们观测到的部落数量就会越少 (不单调), 反之亦然.

所以我们可以考虑二分这个距离, 然后判断哪些人可以构成部落, 用并查集维护即可. 时间复杂度 \(O(n^2 \alpha(n))\).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 1010;
const llf epsilon = 1e-5;

template <typename _T>
_T sqr(_T a) { return a * a; }

class DisjointSet
{
public:
    int par[maxn];
    int n;
    int find(int p)
    {
        if (par[p] == p)
            return p;
        return par[p] = find(par[p]);
    }
    void join(int p, int q)
    {
        p = find(p);
        q = find(q);
        if (p == q)
            return ;
        par[p] = q;
        n -= 1;
        return ;
    }
    void init(int n)
    {
        this->n = n;
        for (int i = 1; i <= n; i++)
            par[i] = i;
        return ;
    }
} djs;

int n, K, x[maxn], y[maxn];
llf dist[maxn][maxn];

bool judge(llf dis)
{
    djs.init(n);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (dist[i][j] <= dis)
                djs.join(i, j);
    if (djs.n >= K)
        return true;
    return false;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &y[i]);
    // Calculating distance
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            dist[i][j] = dist[j][i] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
    // Binary searching, and judging
    llf l = 0, r = 1.0e9;
    while (r - l > epsilon) {
        llf mid = (l + r) / 2;
        if (judge(mid))
            l = mid;
        else
            r = mid;
    }
    // Output
    printf("%.2lf\n", l);
    return 0;
}