시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 128 MB 1909 255 (13%) 227
문제
$N$개의 점 $P_1$, $P_2$, $P_3$, $\dots$, $P_N$이 2차원 좌표 평면에 있다. $P_i$의 좌표를 $(x_i, y_i)$라 할 때, $1$이상 $N$미만인 $i$에 대해 $x_i < x_{i+1}$를 항상 만족한다. $1$번 점에서 시작하여, x좌표가 증가하는 방향으로만 이동하면서 다른 점들을 방문하여 $N$번 점까지 이동한다. 그리고 $N$번 점에서 x좌표가 감소하는 방향으로 다시 $1$번 점으로 되돌아온다. 이 때, $1$번 점을 제외한 나머지 점들은 정확히 한 번만 방문하는 경우 이를 Bitonic Tour라고 한다. 아래 그림은 6개의 점이 있을 때, 가능한 Bitonic Tour의 한 가지 경우를 나타낸다. ![Bitonic Tour의 예](/download_file/2fcc9ce76184e1eb27454da9950756702ea343b573774405010b242d91b7709e/bitonic.png/?show=true) Optimal Bitonic Tour란, 이동한 거리 합이 제일 작은 Bitonic Tour를 의미한다. N개의 점이 주어졌을 때, Optimal Bitonic Tour에서 이동한 거리를 구하는 프로그램을 작성하시오.
입력
첫 줄에 점의 개수를 나타내는 자연수 $N$이 주어진다. ($2 \le N \le 1,000$) 다음 $N$개의 줄에 각 점의 좌표가 주어진다. $i+1$번째 줄에는 $P_i$의 좌표 $x_i$와 $y_i$가 공백으로 구분되어 주어진다. 주어지는 좌표는 $1$이상 $1,000,000$이하다.
출력
첫 줄에 Optimal Bitonic Tour의 이동거리를 소숫점 셋째 자리에서 반올림하여 출력한다.
힌트
#### 예제 입력 ``` 6 1 4 3 1 4 7 6 3 8 6 10 4 ``` #### 예제 출력 ``` 22.53 ```