問題
윤서는 지난 우주여행으로 인하여 KOI우주연합에서 제일 잘나가는 우주여행가가 되었다.
윤서의 가장 큰 취미는 가장 먼 곳까지 여행을 가는 것이었다. 그러나 지난 우주여행 이후로 지친 윤서는 이제 서로 가장 가까운 은하로 여행을 떠나고 싶어졌다.
KOI우주연합은 N개의 은하들로 이루어져 있는데, 그 사이에는 웜홀들이 있엇지만, 윤서는 이제 웜홀 울렁증이 생겨서 그냥 순수하게 우주선을 타고 여행을 하고 싶다.
다행히 윤서는 KOI우주연합의 은하들 중 가장 가까운 두 은하 중 하나에 위치해 있다.
다만 우주선 여행은 연료비가 많이 들고 효율이 떨어지기로 유명하다. 만일 두 별의 위치가 각각 [(X1,Y1), (X2,Y2)]이라면 연료량은
N개의 은하들의 위치 좌표 (X,Y)가 모두 주어졌을 때, 윤서에게 필요한 최소 연료량을 출력하는 프로그램을 작성하시오.
輸入
첫째 줄에 은하의 수 N이 입력된다. (2 ≤ n ≤ 100,000)
두 번째 줄부터 N 줄에 걸쳐 각 은하의 X, Y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이며, 여러 점이 같은 좌표를 가질 수도 있다.
輸出
윤서에게 필요한 최소 연료량을 출력하시오.
子任務
| 編號 | 分數 | 條件 |
|---|---|---|
| #1 | 7分 | n ≤ 1,000 |
| #2 | 23分 | n ≤ 10,000 |
| #3 | 70分 | 추가 제한 없음 |
範例
4
0 0
10 10
0 10
10 0
100
標籤
來源
online contest
需要登入才能撰寫程式碼。