Tsunami

Time limit1sMemory limit128 MB

Summary

Place a warning center and connect cities with cables so every city reaches the center, no city is warned from a city farther from the shore, and total cable length is minimized.

Level: Medium6 of 10
Topics: Graph, Minimum spanning tree, Greedy, Geometry
Solved: No attempts yet

Problem

The country of Cartesia can be described by a single Cartesian plane. The $x$ -axis is the shoreline: the upper half-plane ( $y > 0$ ) is land, and the lower half-plane ( $y < 0$ ) is ocean. Several large cities lie on the mainland, each at a position $(x, y)$ with $y > 0$ .

From time to time a tsunami forms in the ocean near Cartesia, and the whole country can flood. The water starts at $y = 0$ and advances uniformly in the direction of increasing $y$ .

Cartesia wants to build a tsunami warning system made of two kinds of components: a single meteorological center that can detect a tsunami far out at sea, and wired connections that carry the warning from city to city along straight line segments. (No wireless communication is allowed.)

A city is considered safe if it holds the meteorological center, or if it has a direct wired connection to another safe city. In other words, a city is safe whenever there is a multi-hop cable path from it to the meteorological center.

The time to transmit along the cables and through each city is negligible. Even so, politics complicates the engineering. If a city $A$ receives the warning over a wire from a city $B$ , and $B$ is farther from the shore than $A$ , then the residents of $A$ complain: we are closer to the ocean than $B$ , so we should have been warned first! You therefore decide to design the system so that no city ever receives the warning over a wire from a city that is farther from the shore.

Given a description of Cartesia, find the least total length of cable needed to build a tsunami warning system in which every city is safe and no city receives the warning over a wire from a city that is farther from the shore.

Input

The input may contain several test cases.

Each test case begins with a line containing an integer $n$ ( $1 \le n \le 1000$ ), the number of cities.

Each of the next $n$ lines contains two integers $x$ and $y$ ( $-1000 \le x \le 1000$ , $0 < y \le 1000$ ), the location $(x, y)$ of one city.

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

Output

For each test case, print on its own line the minimum total length of cable required to build the tsunami warning system. Print this value as a floating-point number with two digits after the decimal point.

Examples3

Example 1

Input

Expected output

341.42
361.80

Example 2
Input
```
1
5 5
0
```
Expected output
```
0.00
```
Example 3
Input
```
2
0 3
40 3
0
```
Expected output
```
40.00
```