Problem I
Building Roads

A multi-billionaire has a vision to build a completely new city from scratch. After much research and consultations, locations have been selected for all the houses, shopping malls, restaurants, etc. Roads now have to be added to ensure that every location is reachable by any other location, but only the minimum number of roads should be built. For environmental reasons, it is also desirable to minimize the longest travel between two locations. Each road must connect two locations, but roads may cross each other by adding overpasses (so traffic cannot switch to a different road between locations).

What is the minimum length in the longest travel in the road network designed?


The first line of input contains an integer $2 \leq N \leq 200$ specifying the number of locations to follow. Each of the next $N$ lines contains two integers $x_ i$ and $y_ i$ ($-5000 \leq x_ i, y_ i \leq 5000$), specifying the coordinates of the $i$th location. All coordinates are specified in meters, and all locations are distinct.


Output the minimum possible length (in meters) of the longest travel between two locations. Your answer should have a relative or absolute error of less than $10^{-3}$.

Sample Input 1 Sample Output 1
0 0
10 0
0 10
Sample Input 2 Sample Output 2
0 0
10 0
0 10
-10 0
0 -10
10 10
10 -10
-10 10
-10 -10

Please log in to submit a solution to this problem

Log in