Problem K
Association of Camera Makers

ACM (Association of Camera Makers) is a company that produces amazing surveillance cameras. Each camera can produce a live panoramic video feed, giving you a 360-degree view of the surroundings. However, they also have a certain visual range $R$, beyond which the optical resolution is too low to see anything clearly. These cameras are usually used for security purposes, but security can be boring, and watching videos of cats is clearly the best way to dispel boredom.

You live near a huge prairie in which $N$ cats live. Each of these $N$ cats have a favourite spot they will always go to during the day. If money was no object, you’d want to put cameras everywhere so that you can see every cat from every angle, but these cameras are expensive. The greater the visual range $R$, the more expensive the camera. You decide that one camera from ACM is enough, as long as you can see at least $K$ cats from that camera. Fortunately, you can place the camera anywhere you like. Find the minimum visual range of the camera that you must buy in order to be able to see at least $K$ cats.


  • The first line of input contains two integers, $N$ and $K$.

  • The next $N$ lines each contain two integers, $X_ i$ and $Y_ i$, the location (in Cartesian coordinates) of the $i$th cat’s favourite spot.

For all test cases, $2 \le N \le 100\, 000$, $2 \le K \le 200$, and $K \le N$. Also, $0 \le X_ i, Y_ i \le 10^6$. In addition, each test case also satisfies either $K \le 20$ or $N \le 5\, 000$. No two cats have the same favorite spot.


Output a single number $R$ on one line, the minimum visual range required, accurate to two digits after the decimal point.

Sample Data Explanation

Put the camera at $(0, 1)$ with $R = 1.00$ to see $3$ out of $4$ cats.

Sample Input 1 Sample Output 1
4 3
1 1
0 2
0 0
3 2

Please log in to submit a solution to this problem

Log in