Maximize Minimum Distance in Tribes

On a remote island, primitive tribes live in clusters. It is known that the island has exactly n distinct locations where people reside. The island dwellers naturally form tribes (or clusters) according to proximity. In fact, people belonging to the same tribe live near each other. The distance between two different tribes is defined as the minimum Euclidean distance between any two points where one point is from one tribe and the other from the other tribe.

Researchers have discovered that the island residents are divided into exactly k tribes. Your task is to help determine a way of grouping the n locations into exactly k tribes so that the distance between the two closest tribes is as large as possible. In other words, if we define the distance between any two tribes as

$$d(tribe_i, tribe_j)=\min_{a\in tribe_i,b\in tribe_j} \sqrt{(x_a-x_b)^2+(y_a-y_b)^2}, $$

you are to partition the points into k clusters such that the following value is maximized:

$$\min_{1\le i<j\le k} d(tribe_i, tribe_j).$$</p>

Input Format: The first line contains two integers n and k. Then follow n lines, each containing two integers representing the coordinates of a residence on a plane.

Output Format: Output one floating-point number, which is the maximum possible minimum distance between any two tribes. Print the answer with 6 decimal places.

Example:

For instance, consider the following input:

4 2
0 0
0 3
4 0
4 3

A possible optimal grouping is to divide the points into two tribes \({\{(0,0),(0,3)\}\) and \({\{(4,0),(4,3)\}\). The minimum distance between any point in one tribe and any point in the other tribe is 4.000000.

## inputFormat

The first line contains two integers n (the number of locations) and k (the number of tribes).

Each of the next n lines contains two space-separated integers representing the coordinates \(x\) and \(y\) of a location.

## outputFormat

Output a single floating-point number representing the maximum possible minimum distance between any two tribes. The answer must be printed with 6 decimal places.

## sample

4 2
0 0
0 3
4 0
4 3

4.000000

$$