Problem C
Postal Charges

We are in the year 1308. The burgrave of Nuremberg comes to the conclusion that the winding streets of the city are a mess. Thus, he plans to rebuild the whole city in a much larger space with rectangular streets that are parallel to his favourite coordinate system.

It is well known that craftsmen belonging to different guilds should better be living in separate quarters of the city. Of course not all guilds have the same reputation and the quarters for the guilds are to be ordered by reputation. The quarters should also be ordered by the importance for the economy of the city, just to be able to evacuate - in case of an enemy attack or a fire - more important people first. Note that importance is not the same as reputation: e.g. whereas people working in finance have about the lowest possible reputation, they are still important for the economy of the city. In contrast, clerics have a high reputation although the economy could do quite well without them.
The burgrave places the quarter of a guild with reputation $i$ and importance $j$ in the corresponding square with coordinates $[i, i + 1[ \times [j, j + 1[$ , where $i$ and $j$ are integers. No two guilds share the same pair $(i, j)$ .

The only problem is that the burgrave does not know how much to charge for the new postal service. The price of every letter should be the same for all connections within the city. To find a fair price that covers the transportation costs, the burgrave needs to know the average path length of all the mail. A survey has shown that all connections are equally likely with the following exception: Nobody would ever consider to write a letter to someone of a guild with lower or equal reputation or importance than his own. We call a path between two houses admissible if it is not excluded by this condition (see figure on the next page).

Input
The input consists of several test cases, separated from each other by a blank line. The first line of each test case holds an integer $n$ , $2 \le n \le 100800$ . Each of the following $n$ lines contains the coordinates of one house as two decimal numbers $0 \le x, y < 10$ , separated by one space. $x$ , $y$ may have up to $8$ decimal places. Coordinates of some houses may be identical: this corresponds to multi-family houses.

Output
Your program should print one line for each test case and this line should contain the average length of the admissible paths as a decimal number rounded to $8$ digits after the decimal point. As the streets are rectangular and parallel to the coordinate axes, you have to use the Manhattan or $l_1$ -distance for the length of an individual path, i.e. the length of the path $(x_1, y_1) \rightarrow (x_2, y_2)$ is $\vert x_1 - x_2\vert + \vert y_1 - y_2\vert$ . It is guaranteed that there is at least one admissible path.

Fig.: The example city map (clipped) illustrates the last sample input, i.e. 9 quarters/guilds, 6 houses, and all admissible paths.

Sample Input

2
0 0
1 1

4
0 0
1.5 1.7
1.5 1.7
0 0

3
0.2 0.2
1.2 1.2
2.3 0.5

6
2 1
0 0
0 1.5
1.2 1.2
2.5 2.1
0.5 1.7
 

Sample Output

2.00000000
3.20000000
2.00000000
2.95000000