A Star, Not a Tree?

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 100 points in the plane, pick one hub location that minimizes the sum of Euclidean distances to all points, and report the rounded minimum.

Level: Medium6 of 10
Topics: Geometry, Math, Binary search, Implementation
Solved: No attempts yet

Problem

Luke wants to upgrade his home computer network from 10Mbps to 100Mbps. His old network used 10base2 (coaxial) cables, which let him connect any number of computers together in a single line, and Luke was proud that he had solved a nasty NP-complete problem to minimize the total cable length.

Unfortunately, that cabling can no longer be used. The 100Mbps system uses 100baseT (twisted-pair) cables, and each such cable connects exactly two devices: either two network cards, or one network card and a hub (an electronic device that interconnects several cables). Luke has two choices. (1) Buy $2N-2$ network cards, put one or more cards in each computer, and chain them all together. (2) Buy $N$ network cards and one hub, and connect each computer directly to the hub. The first option requires configuring the operating system to forward network traffic, but after installing Winux 2007.2 forwarding stopped working and Luke could not re-enable it. Having never heard of Prim or Kruskal, he settled on the second option: $N$ network cards and one hub.

Luke lives in a loft, so he can run the cables and place the hub anywhere. He will not move his computers. He wants to minimize the total length of cable he must buy.

Equivalently, given the coordinates of $N$ computers in the plane, choose a single hub location $(h_x, h_y)$ that minimizes the total Euclidean distance from the hub to every computer,

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

and report that minimum total.

Input

The first line contains a positive integer $N \le 100$ , the number of computers. Each of the next $N$ lines gives the $(x, y)$ coordinates, in millimetres, of one computer in the room. All coordinates are integers between $0$ and $10\,000$ .

Output

Print one number: the total length of the cable segments, rounded to the nearest millimetre.

Examples3

Example 1

Input

4
0 0
0 10000
10000 10000
10000 0

Expected output

Example 2
Input
```
1
5000 5000
```
Expected output
```
0
```
Example 3
Input
```
2
0 0
0 10000
```
Expected output
```
10000
```