Международная олимпиада АСМ по программированию
(четвертьфинал) 2007
Problem B
Cities
Input from file CITIES.IN in the current folder.
Output to the standard output stream (to the display)
Forward the source code to be solved in CITIES.CPP or CITIES.DPR or CITIES.JAVA
Time limit 30 sec
Memory limit 64 Mb
Due to rapid space exploration there appeared a need of reporting chain development for the cities situated on the Mars.
A signal that can be transmitted at distance R is used for reporting. All the cities situated at the distance not farther then R receive the signal and retransmit it along the chain. The system must work in such a way that all the cities, being reported from any other city, receive the signal.
To be found: a minimum range of transmitters when the reporting chain works.
Input data:
The first number is the amount of tests. In the first line of each test there is number n (1 < n < 1000) – the amount of cities. Further n lines go that contain coordinates of the cities xi and yi (-10000 < xi and yi < 10000, x and y are real). Suppose that all of the cities lie in the same plane.
Example of input data:
2
4
0 0
2 0
0 2
2 3
3
2 0
0 2
4 2
Output data:
For each test in a separate line give a minimum range R (accurate within 2 number signs) of the reporting chain.
Example of output data:
2.24
2.83