|
G |
Magic
Rings Input: Standard Input Output: Standard Output |
|
|
Tanzibal has just reached the last level of the computer
game ‘icpcAxe’. She has used up most of her superpowers in the earlier
levels while defeating the monsters.
Fortunately, there aren’t too many monsters in this level that needs
to be tackled with. |
|
The first step of this level is to spot the locations of
the monsters. After spotting the locations, Tanzibal has to drop the
superpowers one after another on the ground, at different locations, in order
to attack the monsters. A superpower, when dropped at certain point, creates a
magic ring of certain radius. Any monster that lies within the periphery of
this ring will be injured. The radii of the rings generated by the superpowers
are all same, but its value is in Tanzibal’s control. Tanzibal chooses a radius
that is as low as possible. All the rings will have this particular radius that
Tanzibal opts for.
Given the location of N monsters and the number of
superpowers that Tanzibal has at her disposal, can you find out the minimum
radius of the magic rings which would be enough to injure all the monsters.
Input
The first line of input is an integer T(T≤80) that indicates the number of
test cases. Each case starts with two integers N(0< N< 19) and (0< K≤ N). N represents the number of monsters
and K
represents the number of superpowers at hand. The next line contains the
coordinates of the N monsters in the format x1 y1
x2 y2 … xn yn. All the coordinates are integers
in the range [0, 10000].
Note: For 70% of the test cases, (0 < N < 11).
Output
For each case, output the case number, followed by the
minimum radius of the magic rings rounded to 2 decimal places. Look at the
output for sample input for details.
Sample Input Output for
Sample Input
|
3 2 1 0 0 10 0 6 2 0 0 1 1 2 2 10 10 10 11 10 12 4 2 0 0 10 0 5 10 1000 1000 |
Case 1: 5.00 Case 2: 1.41 Case 3: 6.25 |
Problem setter: Sohel Hafiz,
Special Thanks: