Covering Circle

题意翻译

有一个序列 $A_i$，对于每个 $A_i$ 表示一个点 $(x,y)$ 每个测试点会给出参数 $k,l$，你需要选出一个长度为 $l$ 的连续 $A$ 序列，并且找出一个圆满足条件：包含这个连续序列中的 $\geq k$ 个点 输出圆的半径的最小值

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

说明

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