Road network#1445
In a small, but very proud country, there are military bases. The king decided to connect these bases with roads so that it is possible to travel from any base to any other, possibly passing through several roads. An interesting feature of this country is that engineers can only build roads going either from north to south or from west to east. The king instructed the Minister of Transport to develop a plan, and he, in turn, assigned this task to you—the High Programmer of the state. You need to determine the minimum total length of the roads in the constructed road network.
The country uses a Cartesian coordinate system: the axis goes from west to east, and the axis goes from south to north. The sizes of the bases are small enough that they can be considered as points, and the roads as line segments on the plane.
The first line contains the number of bases (1 \leq n \leq 10). Each of the next lines contains the coordinates of a base in the format "", where is the abscissa and is the ordinate, and are integers from to inclusive.
Print one number—the minimum total length of all constructed roads, rounded to exactly digits after the decimal point using standard rounding rules.
Example 1
Possible optimal road networks for the above examples are shown below:
