Cheerio Contest 2 P1 - Cow Pasture

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

To accommodate his cows, Farmer Bob is planning to build a new pasture, which will be circular and centered at point (X, Y). To ensure that the cows have enough food to eat, the pasture must contain at least M patches of grass (each patch is either on the edge or completely inside the pasture). Luckily, Farmer Bob knows the location of N patches of grass, each of which being located at point (x_i, y_i). Can you determine the smallest possible radius of the pasture that satisfies the constraints?

Constraints

For all subtasks:

  • 1 \le M \le N \le 5 \times 10^5
  • -10^4 \le X, Y, x_i, y_i \le 10^4
Points Awarded Additional Constraints
5 points M = 1
10 points No further constraints

Input Specification

The first line of input contains four integers X, Y, N and M.

The next N lines each contain two integers x_i and y_i, the coordinates of the i^\text{th} patch of grass.

Output Specification

Output the smallest possible radius of the pasture. Your answer will be considered correct if it is within 10^{-8} (8 decimal places) of the correct answer.

Sample Input

1 -1 6 6
2 5
-3 -3
3 0
3 0
-2 2
1 -1

Sample Output

6.08276253

Comments

There are no comments at the moment.