All large telescopes in Atacama desert have been interconnected by a cutting edge supercooled quantum cables.
A connection between two different telescopes
may not be a direct one, it usually runs through some other telescopes. The cable between any two directly connected telescopes
follows a straight line and the total length of all cables is minimum possible. All connections are two-way connections.
When the project was completed there was a small suprise for the astronomers. By some luck, European Space Agency (ESA) has found additional funding source and offered to extend the cable connection. The extension consists of installing an additional cable between two carefully chosen telescopes. The two telescopes should be chosen so that in the result the connection diameter of the whole network of telescopes is minimized. The connection diameter of the network is defined as a maximum distance between any two telescopes. The distance between two telescopes is measured along the cables and it is equal to sum of lengths of all cables on the path from one telescope to the other one. When there is more than one path between two telescopes (which will be the case after installation of the additional ESA cable) the distance is always considered to be the length of the shortest possible path between the two telescopes.
You are given the coordinates of all connected telescopes. Determine the minimum possible connection diameter of the telescopes network which can be achieved by installing a single new cable between two telecopes.
The first line contains one positive integer N representing the number of telescopes in the network.
Next, there are N lines, each line specifies the coordinates of one telescope. Each telescope locatation is specified by its x and y
integer coordinates in a square grid. The coordinates are separated by space.
Each coordinate is nonnegative and less than 46341. The value of N does not exceed 300.
The output contains a single line with one float value specifying the minimum possible connection diameter of the telescopes network which can be acieved by installing a new cable anywhere between two telescopes. The value is rounded to two decimal places which will always appear on the output.
7 1 1 6 1 3 2 3 4 2 6 5 6 7 6Output
8.82The result in the example 1 can be achieved by installing the cable between the third and the last telescope in the list.
13 1 1 2 1 3 1 2 2 1 3 2 3 3 3 4 3 5 2 5 3 2 4 5 4 5 5Output
6.61The result in the example 2 can be achieved by installing the cable between the second and the tenth telescope in the list.
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set