P5549 [BJ United Round #3] Observing the Stars

EI is using a telescope to observe stars. There are $n$ stars in the sky, and each star has a 2D Cartesian coordinate $(x,y)$. If the telescope is positioned at $(x_0,y_0)$, it can see all stars satisfying $(x_0-x)^2 + (y_0-y)^2 \le r^2$. The telescope size $r$ can be adjusted. EI wants to know: if he wants to see at least $m$ stars, what is the minimum value to set $r$ to?

The first line contains two positive integers $n,m$, representing the number of stars and the required number of stars to be seen. The next $n$ lines each contain two integers $x,y$, representing the coordinate of one star. It is guaranteed that all star coordinates are pairwise distinct.

Output one line containing one positive real number, representing the minimum radius of the telescope. Let your answer be $a$ and the standard answer be $b$. If $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$ (i.e., the absolute error or relative error does not exceed $10^{-6}$), then your answer is accepted.

| Subtask ID | $n$ | $m$ | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 50$ | $\leq n$ | $10$ | | $2$ | $\leq 200$ | $\leq n$ | $15$ | | $3$ | $\leq 700$ | $\leq n$ | $15$ | | $4$ | $\leq 2000$ | $= n$ | $20$ | | $5$ | $\leq 2000$ | $\leq n$ | $40$ | For $100\%$ of the testdata, it is guaranteed that: $2 \le m \le n \le 2000$. $|x|,|y| \le 10^4$. By: EntropyIncreaser. Translated by ChatGPT 5