트리가 아니라 스타(별) 구조?

루크(Luke)는 집의 컴퓨터 네트워크를 10Mbps에서 100Mbps로 업그레이드하려고 한다. 예전 네트워크는 10base2(동축) 케이블을 썼는데, 이 방식은 여러 대의 컴퓨터를 한 줄로 자유롭게 이어 붙일 수 있었다. 루크는 전체 케이블 길이를 최소화하려고 까다로운 NP-완전 문제를 직접 풀어냈다는 사실을 자랑스러워했다.

그러나 예전 케이블은 그대로 쓸 수 없다. 100Mbps 방식은 100baseT(꼬임쌍선) 케이블을 쓰는데, 이 케이블 한 가닥은 정확히 두 개의 장치만 연결한다. 즉 네트워크 카드 두 개끼리, 또는 네트워크 카드 하나와 허브(hub, 여러 케이블을 서로 이어 주는 전자 장치)를 연결한다. 루크에게는 두 가지 선택지가 있다. (1) 네트워크 카드 $2N-2$개를 사서 각 컴퓨터에 카드를 하나 이상 꽂아 모두 사슬처럼 잇는 방법, 또는 (2) 네트워크 카드 $N$개와 허브 하나를 사서 각 컴퓨터를 허브에 곧바로 잇는 방법이다. 첫 번째 방법은 운영체제에서 네트워크 포워딩을 설정해야 한다. 그런데 Winux 2007.2를 설치한 뒤로 포워딩이 더는 동작하지 않았고, 다시 켜는 방법도 찾지 못했다. 게다가 루크는 프림(Prim)이나 크루스칼(Kruskal) 같은 것을 들어 본 적이 없었기에, 결국 두 번째 방법인 '네트워크 카드 $N$개 + 허브 하나'를 골랐다.

루크는 복층(loft)에 살아서 케이블을 어디로든 배선하고 허브도 어디에나 놓을 수 있다. 다만 컴퓨터의 위치는 옮기지 않는다. 그는 사야 할 케이블의 총 길이를 가장 짧게 하고 싶다.

정리하면, 평면 위에 $N$대의 컴퓨터 좌표가 주어질 때 허브를 놓을 한 점 $(h_x, h_y)$를 자유롭게 골라 각 컴퓨터까지의 유클리드 거리의 합

$$\sum_{i=1}^{N} \sqrt{(h_x - x_i)^2 + (h_y - y_i)^2}$$

을 최소로 만들고, 그 최솟값을 구하면 된다.

첫째 줄에 컴퓨터의 수를 나타내는 양의 정수 $N \le 100$이 주어진다. 이어지는 $N$개의 줄에는 방 안에 있는 각 컴퓨터의 좌표 $(x, y)$가 밀리미터 단위로 주어진다. 모든 좌표는 $0$ 이상 $10,000$ 이하의 정수이다.

케이블 구간들의 총 길이를 가장 가까운 밀리미터(정수)로 반올림하여 한 줄에 출력한다.