Minimum Diameter Sum

A new city has many buildings. To make its administration efficient, the city splits the buildings into two groups, a red one and a blue one. The diameter of a group is the largest distance between two buildings of that group, and it measures how far the group spreads out. The smaller the diameter, the easier the administration. The goal is to find a split whose two diameters have the smallest possible sum.

Each building is a point in the plane, and the distance between two points is the Euclidean distance. The diameter of a point set is the largest distance between two points of the set. You are given a set $P$ of $n$ distinct points in the plane. Split $P$ into two subsets $P_1$ and $P_2$ with $P_1 \neq \emptyset$, $P_2 \neq \emptyset$, $P_1 \cup P_2 = P$, $P_1 \cap P_2 = \emptyset$, and make the diameter of $P_1$ plus the diameter of $P_2$ as small as possible. A subset that holds a single point has diameter $0$.

For example, nine points with integer coordinates are given as in Figure 1(a). Many splits are possible. The split in Figure 1(b) gives the blue points a diameter of $\sqrt{4^2+3^2} = 5$ and the red points a diameter of $\sqrt{5^2+1^2} = \sqrt{26}$, so the sum is $5 + \sqrt{26}$. The split in Figure 1(c) has the sum $4 + \sqrt{34}$, a bit smaller than the sum in Figure 1(b).

Figure 1. (a) The input points. (b), (c) Two splits. In each one the point pair that decides the diameter of a group is joined by a segment in the colour of that group.

The first line holds the number of points $n$ ($2 \le n \le 5{,}000$).

Each of the next $n$ lines holds one point. A line holds the $x$ coordinate and the $y$ coordinate of the point, separated by one space. Both values are integers between $0$ and $10{,}000$, inclusive. The $n$ given points are distinct.

Print the smallest possible sum of the two diameters, rounded to four digits after the decimal point. Always print exactly four digits after the decimal point. For example, if the answer is $2$, print 2.0000.