CF1641F Covering Circle

Sam 开始在沙箱里玩圆形水桶，同时还撒了一些小石子。他的妈妈决定给他买一个新水桶，因此她需要解决如下问题。 给定 $n$ 个具有整数坐标的不同点 $A_1, A_2, \ldots, A_n$。所有点均独立且均匀地从正方形 $[-10^8, 10^8] \times [-10^8, 10^8]$ 内生成。 给定正整数 $k$、$l$，满足 $k \leq l \leq n$。你需要从点数组中选择一个子段 $A_i, A_{i+1}, \ldots, A_{i+l-1}$（对于某个 $1 \leq i \leq n + 1 - l$），并在平面上选择一个圆，使得该圆包含（圆内或圆上）该子段中至少 $k$ 个点。 你需要求出该圆可能的最小半径。

每组测试包含多个测试用例。第一行包含一个整数 $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。

对于每个测试用例，输出一个实数，表示问题的答案。 如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。形式化地，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$ 时，视为正确。

在第一个测试用例中，可以选择子段 $A_1, A_2$，并选取以 $(0, 2)$ 为圆心、半径为 $2$ 的圆。 在第二个测试用例中，可以选择子段 $A_1, A_2, A_3, A_4$，并选取以 $(1, 2)$ 为圆心、半径为 $1$ 的圆。 由 ChatGPT 4.1 翻译