Codeforces Round 773 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

geometry

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Covering Circle

time limit per test

6 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSam 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?

Input

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.

Output

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

Example

Input

43 2 20 00 43 05 4 31 10 02 20 22 08 3 20 31 00 21 10 11 20 01 35 4 41 1-3 32 25 35 5

Output

2.00000000000000000000 1.00000000000000000000 0.50000000000000000000 4.00000000000000000000

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2024 21:11:15 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|