#P2053. Square

Square

Description

Given a square at [0, 1] * [0, 1] that has N points ( P

1

, P

2

, ..., P

N

) in the square (you may assume that different points can be at the same position), we can connect the N points and the four corners of the square with some line segments so that through these segments any two of the N+4 points can reach each other (directly or indirectly). The graph length is defined as the total length of the line segments. When N points' positions are fixed, there must exist a way of connecting them, such that it will make the shortest graph length. We can use LEN (P

1

, P

2

, ..., P

N

) to record the graph length using this way of connecting.

In this situation, LEN (P1

, P

2

, ..., P

N

) is a function of P

1

, P

2

, ..., P

N

. When P

1

, P

2

, ..., P

N

change their positions, LEN (P

1

, P

2

, ..., P

N

) also changes. It's easy to prove that there exist some P

1

', P

2

', ..., P

N

' in the square such that LEN (P

1

', P

2

', ..., P

N

') is at its minimum.

Given the initial positions of N points, your task is to find out N points P1

", P

2

", ..., P

N

" in the square such that |P

1

P

1

"| + |P

2

P

2

"| + ... + |P

N

P

N

"| is minimum and LEN (P

1

", P

2

", ..., P

N

") = LEN (P

1

', P

2

', ..., P

N

') . You are requested to output the value of |P

1

P

1

"| + |P

2

P

2

"| + ... + |P

N

P

N

"|, where |PiPi"| is the distance between Pi and Pi".

For example, Figure-1 gives the initial position of P1

and the way of connecting to obtain LEN (P

1

). In Figure-2, it gives the position of P

1

", which is at the center of the square, and the way of connecting to obtain LEN (P

1

"). It can be proved that LEN (P

1

") = LEN (P

1

’); your job is to output the distance between P

1

and P

1

".

Input

The input consists of several test cases. For each test case, the first line consists of one integer N (1 <= N <= 100), the number of points, and N lines follow to give the coordinates for every point in the following format:

x y

Here, x and y are float numbers within the value [0, 1].

A test case of N = 0 indicates the end of input, and should not be processed.

Output

For each test case, output the value of |P

1

P

1

"| + |P

2

P

2

"| + ... + |P

N

P

N

"|. The value should be rounded to three digits after the decimal point.

1
0.2 0.5
2
0 0.5
0.5 0.5
0
0.300
0.500

Source

Beijing 2004