돌 모으기

$N$개의 돌이 좌표계에 어지럽게 흩어져 있다. 각 돌에는 좌표 ($x_i$,$y_i$)가 있다. 이제 돌을 한데 모을 때가 되었고, 이를 돕기 위해 매우 똑똑한 돌 수거 기계를 마련했다.

기계를 작동하기 전에 수거 지점 $S$이라고 부를 점을 하나 선택해야 한다. 이 점은 기계가 출발하며 수거한 돌을 놓을 곳이다. 이 점은 x축 위 어딘가에 있어야 한다. 기계는 수거 지점 $(S,0)$에서 출발한 뒤 모든 돌을 수거하여 수거 지점에 놓는다. 기계는 한 번에 돌 하나만 운반할 수 있다.

연료는 비싸므로 조금 영리하게 처리하려고 한다. 기계가 작동을 시작하면 항상 모든 돌을 최적으로 수거한다는 것을 알고 있지만, 기계가 이동한 총거리가 최소가 되도록 수거 지점을 선택하는 것은 당신의 몫이다. 수거 지점을 최적으로 선택할 때 이 거리는 얼마인가? 돌과 기계는 좌표평면 위의 점으로 간주할 수 있다.

채점

해결책은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$30$| 모든 돌이 x축 위에 있으며 $N \leq 1000$이다.

$2$ |$30$| 모든 돌이 x축 위에 있다.

$3$ |$40$| 추가 제한이 없다.

첫 번째 줄에는 돌의 개수를 나타내는 정수 $N$ ($1 \leq N \leq 10^5$)이 주어진다.

이어서 돌의 좌표를 나타내는 부동소수점 수의 쌍 $x_i y_i$가 $N$개의 줄에 걸쳐 주어진다. 입력의 모든 돌은 원점에서 최대 100 길이 단위만큼 떨어져 있다.

기계가 모든 돌을 수거한 뒤 이동한 총거리로 가능한 최솟값을 하나의 정수로 출력한다. 절대 오차가 $10^{-4}$보다 작으면 정답으로 간주한다.

팁: 답이 클 때에도 프로그램이 충분히 많은 소수 자릿수를 출력하도록 하라.

그림은 기계의 이동 거리를 최소로 만드는 출발점의 가능한 선택인 x = 1.25을 보여 준다. 기계는 왼쪽 돌을 가져오기 위해 0.5 길이 단위만큼 이동해야 하고, 그다음 오른쪽 돌을 가져오기 위해 0.5 길이 단위만큼 이동해야 한다.

그림은 x = 2.0에 있는 기계의 최적 출발 위치를 보여 준다. 이동한 총거리는 $4\cdot\sqrt{2^2 + 1} = 8.94427191...$이다.