| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 410 | 195 | 152 | 51.007% |
흐즈로는 어느 날 2차원 메타버스를 방문하였습니다. 2차원 메타버스에서 두 점 사이의 거리는 유클리드 거리 $d(A,B)=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}$로 정의합니다. 메타버스에는 $n$개의 국가가 있는데, 각 국가는 한 점 $(x_i,y_i)$로 구성되어 있습니다. 메타버스 세계의 평화 협정에 따라 서로 다른 두 국가가 같은 점을 차지하지 않으며, 어떤 세 국가도 한 직선 위에 있지 않습니다. 흐즈로는 2차원 메타버스에서 세계 일주를 하면 재미있을 것으로 생각하였습니다. 흐즈로의 세계 일주는 다음과 같은 규칙을 따릅니다.
흐즈로는 이 규칙에 따라 세계 일주를 할 수 있을지 궁금했습니다. 흐즈로가 세계 일주를 할 수 있는지 판단하고, 할 수 있다면 세계 일주의 최소 비용을 출력해 주세요.
첫 번째 줄에 국가의 개수 $n$이 주어집니다. ($3 \le n \le 10$)
두 번째 줄부터 $n$개의 줄에 걸쳐 각 줄에 국가가 차지하는 점의 좌표에 해당하는 두 정수 $x_i$와 $y_i$가 공백으로 분리되어 주어집니다. ($-10^6 \le x_i,y_i \le 10^6$)
서로 다른 두 국가가 같은 점을 차지하지 않으며, 어떤 세 국가도 한 직선 위에 있지 않음이 보장됩니다.
흐즈로가 규칙에 따라 세계 일주를 할 수 있다면, 그 최소 비용을 한 줄에 출력합니다. 규칙에 따른 세계 일주가 불가능하다면, $-1$을 한 줄에 출력합니다.
문제의 정답과 출력 간의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하일 경우 정답으로 인정됩니다.
4 0 1 0 -1 2 0 -2 0
8.944271909999
$(0,1) \ \to \ (2,0) \ \to \ (0,-1) \ \to \ (-2,0) \ \to \ (0,1)$의 경로를 따르면 비용은 $4\sqrt{5} \approx 8.944271909999$가 됩니다. 비용을 $4\sqrt{5}$보다 작게 만들 수 없으므로 정답은 $4\sqrt{5}$가 됩니다.
이때, $(0,1) \ \to \ (0,-1) \ \to \ (2,0) \ \to \ (-2,0) \ \to \ (0,1)$의 경로는 $(0,0)$을 두 번 지나게 되므로 규칙에 어긋납니다.