← 返回题目列表

Codeforces · 1641/F

F. 覆盖圈

中文机器翻译题面 查看原题

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$$$),以及平面上的一些圆,其中包含所选子段的 $$$\geq 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]$$$ 上的均匀分布生成的。这是唯一的此类测试,您的解决方案必须通过它。

在此问题中,黑客被禁用。

输出

对于每个测试用例,打印一个实数——问题的答案。

如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。正式让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$,您的答案将被视为正确。

示例

输入 #1

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

输出 #1

2.00000000000000000000
1.00000000000000000000
0.50000000000000000000
4.00000000000000000000

注意

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

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