CF1641F.Covering Circle

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?

山姆在沙箱里玩圆形水桶，同时撒下了一些小石子。他的妈妈决定给他买一个新水桶，因此需要解决以下问题。

给定 $n$ 个互异的、具有整数坐标的点 $A_1, A_2, \ldots, A_n$。所有点均独立、均匀地从正方形区域 $[-10^8, 10^8] \times [-10^8, 10^8]$ 中生成。

给定正整数 $k$ 和 $l$，满足 $k \leq l \leq n$。你需要从点列中选出一个长度为 $l$ 的连续子段 $A_i, A_{i+1}, \ldots, A_{i+l-1}$（其中 $1 \leq i \leq n + 1 - l$），并选取平面上的一个圆，使得该圆包含所选子段中至少 $k$ 个点（点可在圆内或圆上）。

该圆可能的最小半径是多少？

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.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$l$、$k$（$2 \leq k \leq l \leq n \leq 50\,000$，且 $k \leq 20$）。

接下来的 $n$ 行中，每行包含两个整数 $x_i$、$y_i$（$-10^8 \leq x_i, y_i \leq 10^8$），表示点 $A_i$ 的坐标。保证所有点互不相同，且独立地从 $[-10^8, 10^8] \times [-10^8, 10^8]$ 上的均匀分布中生成。

保证所有测试用例的 $n$ 值之和不超过 $50\,000$。

在第一个测试用例中，为简化起见，点并非从 $[-10^8, 10^8] \times [-10^8, 10^8]$ 上的均匀分布中生成。这是唯一一个这样的测试用例，你的解法必须通过它。

本题禁用 Hack。

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}$.

对于每个测试用例，输出一个实数——该问题的答案。

若你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。形式化地，设你的答案为 $a$，评测组的答案为 $b$，当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$ 时，你的答案被视为正确。

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$.

在第一个测试用例中，我们可以选择子段 $A_1, A_2$ 以及以 $(0, 2)$ 为圆心、半径为 $2$ 的圆。

在第二个测试用例中，我们可以选择子段 $A_1, A_2, A_3, A_4$ 以及以 $(1, 2)$ 为圆心、半径为 $1$ 的圆。