309202: CF1641F. Covering Circle
Memory Limit:256 MB
Time Limit:6 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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