[KOITP] 지름(Not Solved)

출    처 : http://koitp.org/problem/ICPC_2016DAJI_DIAMETER/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	79	7 (9%)	7

문제

2차원 좌표 평면에 $n$개의 점이 주어진다. 주어지는 점을 두 개의 집합으로 나눌 수 있다. 한 집합 내에 가장 먼 두 점의 거리를 지름(diameter)라고 하는데, 두 집합의 지름 합을 최소화하는 프로그램을 작성하시오

예를 들어, (a)처럼 9개의 점이 좌표 평면에 있다고 하자. 9개의 점을 두 집합으로 나누는 방법은 여러 가지가 있다. (b)처럼 빨간 점 집합, 파란 점 집합, 두 개의 집합으로 나누는 경우 파란 점 집합의 지름이 $\sqrt{4^2+3^2}=5$가 되고, 빨간 점 집합의 지름이 $\sqrt{5^2+1^2}=\sqrt{26}$이고, 합은 $5+\sqrt{26}$이 된다. 하지만 (c)처럼 두 집합으로 나눌 때, 지름의 합은 $4+\sqrt{34}$가 되고 이 때 (b)보다 합이 더 작게 된다.

입력

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

다음 $n$개의 줄에 걸쳐 각 점의 $x$-좌표와 $y$-좌표가 공백으로 구분되어 주어진다. 주어지는 좌표의 범위는 0이상 10,000이하이다.

출력

첫 줄에 주어진 $n$개의 점들을 두 집합으로 나눠 두 집합의 지름 합을 최소화할 때, 최소값을 출력한다. 정답과 차이가 절대 오차 ${10}^{-3}$ 이내인 경우 정답으로 처리된다.

힌트

예제 입력 1

3
0 1
3 2
3 0

예제 출력 1

2.0000

예제 입력 2

9
2 2
6 1
7 3
6 5
3 5
1 4
2 6
5 7
4 3

예제 출력 2

6.0827