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 quar-
ters 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) × [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).
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 ≤ n ≤ 100800. Each of the following n lines contains the
coordinates of one house as two decimal numbers 0 ≤ 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.
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 l1 -distance for
the length of an individual path, i.e. the length of the path (x1 , y1 ) → (x2 , y2 ) is |x1 − x2 | + |y1 − y2 |.
It is guaranteed that there is at least one admissible path.
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
2.00000000 3.20000000 2.00000000 2.95000000
The figure of sample input is in the pdf file.
Migrated from old NTUJ.
SWERC 2008
| No. | Testdata Range | Score |
|---|