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
Nchange 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
1P
1"| + |P
2P
2"| + ... + |P
NP
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
1P
1"| + |P
2P
2"| + ... + |P
NP
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
1and 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 yHere, 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
1P
1"| + |P
2P
2"| + ... + |P
NP
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