Description

Congcong discovered that the savages on a deserted island always live in groups. However, not all savages on the island belong to the same tribe; they form their own tribes and different tribes often fight. But all of this is a mystery—Congcong does not know how the tribes are distributed.

The good news is that Congcong obtained a map of the island. The map marks $n$ dwelling locations (viewed as coordinates on a plane). We know that members of the same tribe live close to each other. We define the distance between two tribes as the distance between the closest pair of dwellings, one from each tribe. Congcong also learned an important fact—the savages are divided into $k$ tribes in total. This is great news. He wants to extract detailed information about all tribes from this data. He is trying the following approach:

For any partition of the dwellings into tribes, we can compute the distance between any two tribes. Congcong wants to find a partition such that the closest pair of tribes are as far apart as possible.

For example, the left figure below shows a good partition, while the right one does not. Please write a program to help Congcong solve this problem.

Input Format

The first line contains two integers $n$ and $k$, representing the number of dwelling locations and the number of tribes.

The next $n$ lines each contain two integers $x$, $y$, giving the coordinates of a dwelling.

Output Format

Output a single real number: under the optimal partition, the distance between the two closest tribes, rounded to two decimal places.

4 2
0 0
0 1
1 1
1 0

1.00

9 3
2 2
2 3
3 2
3 3
3 5
3 6
4 6
6 2
6 3

2.00

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $2 \leq k \leq n \leq 10^3$, $0 \leq x, y \leq 10^4$.

Translated by ChatGPT 5