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$$$ 为半径的圆。