Square#3502

Square

1 second

64 megabytes

Medium

Given a square at $[0, 1] \times [0, 1]$ [0, 1] \times [0, 1] that has $N$ points ( $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, 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$ N+4 points can reach each other, directly or indirectly. The graph length is defined as the total length of the line segments. When the positions of $N$ points are fixed, there must exist a way of connecting them such that it yields the shortest graph length. We use $LEN (P_{1}, P_{2}, \dots, P_{N})$ \mathrm{LEN}(P_1, P_2, \ldots, P_N) to record the graph length using this way of connecting.

In this situation, $LEN (P_{1}, P_{2}, \dots, P_{N})$ \mathrm{LEN}(P_1, P_2, \ldots, P_N) is a function of $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, P_N. When $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, P_N change their positions, $LEN (P_{1}, P_{2}, \dots, P_{N})$ \mathrm{LEN}(P_1, P_2, \ldots, P_N) also changes. It's easy to prove that there exist some $P_{1}^{'}, P_{2}^{'}, \dots, P_{N}^{'}$ P_1', P_2', \ldots, P_N' in the square such that $LEN (P_{1}^{'}, P_{2}^{'}, \dots, P_{N}^{'})$ \mathrm{LEN}(P_1', P_2', \ldots, P_N') is at its minimum.

Given the initial positions of $N$ points, your task is to find $N$ points $P_{1}^{''}, P_{2}^{''}, \dots, P_{N}^{''}$ P_1'', P_2'', \ldots, P_N'' in the square such that $∣ P_{1} P_{1}^{''} ∣ + ∣ P_{2} P_{2}^{''} ∣ + \dots + ∣ P_{N} P_{N}^{''} ∣$ |P_1P_1''| + |P_2P_2''| + \cdots + |P_NP_N''| is minimized and $LEN (P_{1}^{''}, P_{2}^{''}, \dots, P_{N}^{''}) = LEN (P_{1}^{'}, P_{2}^{'}, \dots, P_{N}^{'})$ \mathrm{LEN}(P_1'', P_2'', \ldots, P_N'') = \mathrm{LEN}(P_1', P_2', \ldots, P_N'). You are requested to output the value of $∣ P_{1} P_{1}^{''} ∣ + ∣ P_{2} P_{2}^{''} ∣ + \dots + ∣ P_{N} P_{N}^{''} ∣$ |P_1P_1''| + |P_2P_2''| + \cdots + |P_NP_N''|, where $∣ P_{i} P_{i}^{''} ∣$ |P_iP_i''| is the distance between $P_{i}$ P_i and $P_{i}^{''}$ P_i''.

For example, Figure-1 gives the initial position of $P_{1}$ P_1 and the way of connecting to obtain $LEN (P_{1})$ \mathrm{LEN}(P_1). In Figure-2, it gives the position of $P_{1}^{''}$ P_1'', which is at the center of the square, and the way of connecting to obtain $LEN (P_{1}^{''})$ \mathrm{LEN}(P_1''). It can be proved that $LEN (P_{1}^{''}) = LEN (P_{1}^{'})$ \mathrm{LEN}(P_1'') = \mathrm{LEN}(P_1'); your job is to output the distance between $P_{1}$ P_1 and $P_{1}^{''}$ P_1''.

Input

The input consists of several test cases. For each test case, the first line consists of one integer $N$ ( $1 \leq N \leq 100$ 1 \leq N \leq 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 floating-point numbers within the range $[0, 1]$ .

A test case with $N = 0$ 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}^{''} ∣ + \dots + ∣ P_{N} P_{N}^{''} ∣$ |P_1P_1''| + |P_2P_2''| + \cdots + |P_NP_N''|. The value should be rounded to three digits after the decimal point.

Examples

Example 1