ZOJ Problem Set - 3257
Once upon a time, there was a magical land, towers were used as information transmit bases.
So as the name, the magical land was so magical that no one had found out the edge of it, but everyone knew that it might be endless. How can they knew that?
The answer is simple, the magical land had a "origin point", when standing on the point, people can not see any boundary of the land. We know that most people's sight limit in magical land was within 10000(Units can be ignored).
So, when standing on the origin point, people can see many towers standing on the ground, connecting each part of the magical land, all shining, embellishing the magnificent scenery.
But the towers were not omnipotent, their transmission of information cost much. So the Magical Land Information Transmit Department(MLITD) implemented a very powerful Information Transmit Protocol(ITP), their Information Transmit System(ITS) was built on this magical protocol, provided a good information transmit service.
Although the magical land had gone with the wind, we still want to recover the ITS, because it has great value to our modern systems. From the record, we discovered that the towers stand on some distinct points, which can be described as (x, y)(0 < (x2 + y2)1/2 <= 10000). Before the system's establishment, every two towers(Temporarily mark them as tower A and tower B, their positions are (xA, yA) and (xB, yB) ) took a cost of (xA - xB)2 + (yA - yB)2 + |xA - yB| * |xB - yA| TU(From the record, TU was the units of information transmit measurement).
During the system's establishment, MLITD would first examine all pairs of towers. They temporarily mark them as tower A and tower B, then they check each path between tower A and tower B, including the direct transmission and the transmission through some other towers. When checking a path between tower A and tower B, MLITD recorded the largest cost in this path, as the path's bottleneck value. And when all the checking finished, MLITD would select a path which had the minimum bottleneck value, establish a transmit link using the ITP, namely the cost between tower A and tower B in ITS.
To help us recover the ITS, we want you to calculate the overall cost when using ITS to transmit information.
There are several test cases (no more than 25).
In each case, there will be one number in the first line, N (integer, 1 <= N <= 1000), which represents the number of towers.
The next N lines describe the positions of each tower, each line has two integers x and y (0 < (x2 + y2)1/2 <= 10000), separated by a space.
For each test case, just output the overall cost when using ITS.
5 1 5 5 4 2 7 5 2 9 8
Author: FAN, Yuzhe
Source: ZOJ Monthly, September 2009