지름의 합 최소화

새로 지은 도시에는 건물이 많다. 행정 효율을 높이려고 도시는 건물을 빨간 그룹과 파란 그룹, 두 그룹으로 나누려고 한다. 한 그룹의 지름은 그 그룹에 속한 두 건물 사이 거리의 최댓값이고, 그룹이 공간에 얼마나 넓게 퍼져 있는지를 재는 기준이다. 지름이 작을수록 행정이 쉬워진다. 두 그룹의 지름을 더한 값이 가장 작아지는 분할을 찾아야 한다.

건물은 평면 위의 점 하나로 나타내고, 두 점 사이의 거리는 유클리드 거리다. 점 집합의 지름은 그 집합에 속한 두 점 사이 거리의 최댓값이다. 평면 위에 서로 다른 점 $n$개로 이루어진 집합 $P$가 주어진다. $P_1 \neq \emptyset$, $P_2 \neq \emptyset$, $P_1 \cup P_2 = P$, $P_1 \cap P_2 = \emptyset$을 만족하도록 $P$를 두 부분집합 $P_1$과 $P_2$로 나누고, $P_1$의 지름과 $P_2$의 지름을 더한 값을 최소로 만들어라. 부분집합이 점 하나로만 이루어져 있으면 그 지름은 $0$이다.

예를 들어 정수 좌표를 가진 점 아홉 개가 그림 1(a)처럼 주어졌다고 하자. 나누는 방법은 여러 가지다. 그림 1(b)처럼 나누면 파란 점의 지름은 $\sqrt{4^2+3^2} = 5$, 빨간 점의 지름은 $\sqrt{5^2+1^2} = \sqrt{26}$이므로 합은 $5 + \sqrt{26}$이다. 그림 1(c)의 분할은 지름의 합이 $4 + \sqrt{34}$로, 그림 1(b)보다 조금 작다.

그림 1. (a) 입력으로 주어진 점. (b), (c) 두 가지 분할. 각 그룹의 지름을 결정하는 점 쌍을 그룹과 같은 색 선분으로 이어 두었다.

첫째 줄에 점의 개수 $n$이 주어진다 ($2 \le n \le 5{,}000$).

다음 $n$개 줄에 점이 한 줄에 하나씩 주어진다. 각 줄에는 점의 $x$좌표와 $y$좌표가 공백 하나로 구분되어 주어지며, 두 값 모두 $0$ 이상 $10{,}000$ 이하의 정수다. 주어지는 점 $n$개는 서로 다르다.

첫째 줄에 두 그룹의 지름을 더한 값의 최솟값을 소수점 아래 넷째 자리까지 반올림해 출력한다. 소수점 아래 자릿수는 항상 넷이어야 한다. 예를 들어 답이 $2$이면 2.0000을 출력한다.