In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
The mayor of Bytetown is planning to create a bus transportation network. The network will consist of bus stops and bus lines. Two of the bus stops, denoted as and , will be selected as transfer nodes and each of the remaining stops will be directly connected to either or (but not to both of them). Additionally, there will be a bus line connecting both transfer nodes. Due to lack of funds no other bus connections will be created.
The travel distance between two bus stops located at coordinates and that have a direct bus connection equals . If two bus stops are both connected to the same transfer node, the travel distance between them squals the sum of their distances to that transfer node. If two bus stops are connected to different transfer nodes, the travel distance between them equals the sum of their distances to the respective transfer nodes plus the distance between the transfer nodes.
Write a program which:
The first line of the standard input contains one integer (), the number of bus stops in Bytetown. Each of the following lines contains two positive integers not exceeding , the coordinates of a bus stop. There is at most one bus stop located in each point.
Your program should write to the standard output one integer: the maximum distance between any two bus stops assuming an optimal selection of transfer nodes and connections between pairs of bus stops.
For the input data:
6 1 7 16 6 12 4 4 4 1 1 11 1
the correct result is:
The figure corresponds to the sample data. The stops no. 3 and 4 are the transfer nodes.
Task originating from one of the IOI's.