Underground Cables

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 1000 points, connect them all with straight line segments of minimum total length, with no two segments crossing.

Level: Medium4 of 10
Topics: Minimum spanning tree, Graph, Geometry, Sorting
Solved: No attempts yet

Problem

A city wants to get rid of its unsightly power poles by moving all of its power cables underground. It has a list of points that all need to be connected, but there are some limitations. The tunneling equipment can only move in straight lines between points, and there is room for only one underground cable at any location other than the given points, so no two cables may cross.

Given the list of points, what is the least total length of cable needed so that every pair of points is connected, either directly or indirectly through other points?

Input

The input consists of several test cases. Each test case begins with an integer $N$ ( $2 \le N \le 1000$ ), the number of points in the city. Each of the next $N$ lines contains two integers $X$ and $Y$ ( $-1000 \le X, Y \le 1000$ ), the $(X, Y)$ location of a point.

The input ends with a line containing a single $0$ .

Output

For each test case, output on its own line a single real number: the least total length of cable needed to connect all of the points. Print this value rounded to two decimal places.

Examples3

Example 1

Input

Expected output

30.00
14.14

Example 2
Input
```
2
0 0
5 0
0
```
Expected output
```
5.00
```
Example 3
Input
```
3
0 0
3 0
7 0
0
```
Expected output
```
7.00
```