- Time limit: 2.00 s
- Memory limit: 512 MB
Uolevi has been hired to design the telecommunication antennas for the new 6G network. There will be n masts numbered 1,2,\dots,n where the antennas will be placed. The i-th mast is located at coordinates (x_i, y_i). Uolevi's task is to find the minimum distance the antennas need to cover so that the masts form a connected network. That is, for each pair of antennas, there should be a path connecting them that jumps along the antennas and no jump is longer than the coverage distance.
Input
First line contains a single integer n. The i-th of next n following lines contains two integers x_i and y_i.
Output
Print the minimum distance the antennas need to cover. The answer is considered correct if the relative or absolute error does not exceed 10^{-6}.
Constraints
- 1 \leq n \leq 1000
- -10^5 \leq x_i, y_i \leq 10^5
Example 1
Input:
3 0 0 1 1 2 0
Output:
1.41421356237309504880
Example 2
Input:
10 1.8568923303 6.8853148851 7.1589123998 6.9450347477 2.4712739299 -2.3123658325 -4.0493078929 -8.8657404813 -4.5468741052 -0.4466977651 6.2433745330 -0.4004565695 -2.1443041341 6.7215753809 -3.2520767671 2.9634375315 -2.6351692527 9.1431030903 -7.1929844479 7.4017450254
Output:
8.43373300459665028398
Example 3
Input:
2 -100000 -100000 100000 100000
Output:
282842.71247461900972552939