Going to FlatLand

Submit solution

Points: 35
Time limit: 1.0s
Memory limit: 64M

Problem type

One of the most fascinating newly discovered planets was called FlatLand. As the name implies, the planet was a 2 dimensional planet inhabited by flat beings like squares, circles, triangles and many more.

FlatLand is a relatively new planet, it isn't very evolved yet, they have just begun installing antennas for their new TV network and want to cover all of the houses in any given city. Each of their antennas' covering range can cover a circular area around the antenna's position, but they have to build all of the antennas with the same power so they will all have the same covering radius. Knowing that in each city, all of the houses are collinear (lie on a the same line), and the antennas can be put anywhere, and knowing how many antennas they intend to build; they want to minimize the covering radius of the antennas, in order to minimize the cost. Can you help them?

You are given the location of each house in the city, and given the number of antennas to be placed. Can you calculate the shortest possible covering radius for the antennas?

Input Specification

The first line contains a single integer \(T\), the number of test cases. In each test case, representing a city, the first line contains two space separated integers \(N\), \(K\) (\( 1 \le K \le N \le 10^5 \)), where \(N\) is the number of houses in the city and \(K\) is the number of antennas they intend to build, the second line contains \(N\) space separated integers \(L_i\) (for \(1 \leq i \leq N\) and \(1 \le L_i \le 10^9\)) representing the location of the houses in this city.

Output Specification

For each test case, print the answer with 3 decimal digits in its fractional part, which is the minimum covering radius of the antennas.

Sample Input

4 2
1 10 15 20
6 2
1 5 5 10 20 30

Sample Output



In the first sample: The antennas are placed at points \(5.5\) and \(16\).

In the second sample: The antennas are places at the points \(5\) and \(25\).


  • 1
    manal12  commented on May 24, 2021, 6:31 p.m.

    I don't understand the problem!