Covering Circle
Contest: Codeforces Round 773 (Div. 1)
Difficulty rating: 3500
Tags: geometry

Sam started playing with round buckets in the sandbox, while also scattering pebbles. His mom decided to buy him a new bucket, so she needs to solve the following task.

You are given $$$n$$$ distinct points with integer coordinates $$$A_1, A_2, \ldots, A_n$$$. All points were generated from the square $$$[-10^8, 10^8] \times [-10^8, 10^8]$$$ uniformly and independently.

You are given positive integers $$$k$$$, $$$l$$$, such that $$$k \leq l \leq n$$$. You want to select a subsegment $$$A_i, A_{i+1}, \ldots, A_{i+l-1}$$$ of the points array (for some $$$1 \leq i \leq n + 1 - l$$$), and some circle on the plane, containing $$$\geq k$$$ points of the selected subsegment (inside or on the border).

What is the smallest possible radius of that circle?

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Descriptions of test cases follow.

The first line of each test case contains three integers $$$n$$$, $$$l$$$, $$$k$$$ ($$$2 \leq k \leq l \leq n \leq 50\,000$$$, $$$k \leq 20$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^8 \leq x_i, y_i \leq 10^8$$$) — the coordinates of the point $$$A_i$$$. It is guaranteed that all points are distinct and were generated independently from uniform distribution on $$$[-10^8, 10^8] \times [-10^8, 10^8]$$$.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$50\,000$$$.

In the first test, points were not generated from the uniform distribution on $$$[-10^8, 10^8] \times [-10^8, 10^8]$$$ for simplicity. It is the only such test and your solution must pass it.

Hacks are disabled in this problem.

Output format:
For each test case print a single real number — the answer to the problem.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$. Formally let your answer be $$$a$$$, jury answer be $$$b$$$. Your answer will be considered correct if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can select subsegment $$$A_1, A_2$$$ and a circle with center $$$(0, 2)$$$ and radius $$$2$$$.

In the second test case, we can select subsegment $$$A_1, A_2, A_3, A_4$$$ and a circle with center $$$(1, 2)$$$ and radius $$$1$$$.

Example input:
4
3 2 2
0 0
0 4
3 0
5 4 3
1 1
0 0
2 2
0 2
2 0
8 3 2
0 3
1 0
0 2
1 1
0 1
1 2
0 0
1 3
5 4 4
1 1
-3 3
2 2
5 3
5 5

Example output:
2.00000000000000000000
1.00000000000000000000
0.50000000000000000000
4.00000000000000000000

Editorial:
If the answer is $$$r$$$ let's consider $$$n$$$ circles $$$C_1, C_2, \ldots, C_n$$$ with centers $$$A_1, A_2, \ldots, A_n$$$ and radius $$$r$$$. If a required circle with radius $$$r$$$ exists it should be true, that $$$k$$$ circles $$$C_{i_1}, C_{i_2}, \ldots, C_{i_k}$$$ has non empty intersection for some $$$i_1 < i_2 < \ldots < i_k$$$ and $$$i_k - i_1 < l$$$. For some $$$1 \leq h \leq k$$$ we can find intersection point of these circles on circle $$$C_{i_h}$$$. Let's define $$$j = i_h$$$.
Let's define $$$f(j)$$$ as the minimal possible $$$r$$$, such that there exists $$$k$$$ circles $$$C_{i_1}, C_{i_2}, \ldots, C_{i_k}$$$ and $$$i_k - i_1 < l$$$, such that $$$j = i_h$$$ for some $$$1 \leq h \leq k$$$ and these circles intersect on circle $$$C_j$$$. Then the answer to the problem is $$$\min_{1 \leq j \leq n} f(j)$$$.
Let's make a procedure to check, that $$$f(j) \leq x$$$ for some $$$x$$$. To check that let's consider circles $$$C_{j-l+1}, \ldots, C_j, \ldots, C_{j+l-1}$$$ with centers $$$A_{j-l+1}, \ldots, A_j, \ldots, A_{j+l-1}$$$ and radius $$$x$$$. Each of them intersect with $$$C_j$$$ with some arc (circular segment). We can find all these arcs. Let's now make scanline and mantain all indices of arcs covering the current point. With segment tree with lazy propagation we can check if there exists $$$k - 1$$$ indices with difference at most $$$l - 1$$$. The complexity of this check is $$$O(s \log{n})$$$, where $$$s$$$ is the number of arcs.
Let's iterate $$$j$$$ from $$$1$$$ to $$$n$$$ and maintain the current answer $$$r$$$. Initially let's initialize $$$r$$$ with $$$\sqrt{2} \cdot 10^8 \cdot \frac{\sqrt{l-1}}{\sqrt{k-1}}$$$ (it's easy to prove that the answer can't be bigger than these constant for any points). Now if we have some $$$j$$$ let's firstly check, that $$$f(j) \leq r$$$ (if not — the answer won't be updated), if it is true — let's make a binary search to find a new answer. The only problem is — the number of arcs can be big. Let's note, that $$$C_i$$$ makes an arc on $$$C_j$$$ if and only if $$$|A_i A_j| \leq 2x$$$. So let's make an infinite grid with step $$$2r$$$ and maintain a set of points in each square. Also, we should maintain points from the segment $$$[j - l + 1, j + l - 1]$$$. After that, we can only check indices, that are in the same square as the point $$$A_j$$$ and in $$$8$$$ neighboring squares. It's easy to prove, that if $$$r \leq \sqrt{2} \cdot 10^8 \cdot \frac{\sqrt{l-1}}{\sqrt{k-1}}$$$ the expected number of points in each grid square is $$$O(k)$$$. In practice, the average number of points to check is around $$$4k \sim 5k$$$. So we can find these candidate points and then use in procedures to check, that $$$f(j) \leq x$$$, which will work in $$$O(k \log{n})$$$. If $$$r$$$ is changed we can reconstruct all grid in $$$O(l)$$$.
Due to all points are random the expected number of times when $$$r$$$ will change is $$$O(\log{n})$$$ (famous Blogewoosh #6 idea). So the complexity of this solution is $$$O(n k \log{n} + k \log{n} \log{\varepsilon^{-1}})$$$.