Brickgao used to be a real tall, wealthy, handsome man and you might know him well. If you don't, please draw attention to the details below.
Brickgao tried his fortune in investment of golden bricks with his two partners LS and Jne. Because he knew little about investment he gave his total trust and bank savings to his two partners who looked smart.
However, due to the bad luck and lack of business skills, LS and Jne used up Brickgao's fund, and nothing in return. Their investment failed and the three become diaosi.
Brickgao had no other choice but to earn a living as a construction worker and he found his place on a building site moving bricks which of course was not golden ones. There were many brick fragment scattered on the site and workers had to move them to the building that under construction. Brickgao was made to cope with the task.
The problem is that the Brickgao couldn’t carry more than two bricks at a time since they were too heavy. Also, if he had taken a brick, he couldn’t put it anywhere except the goal building — his inherent sense of order does not let him do so.
You are given N pairs of coordinates of the bricks and the coordinates of the goal building. It is known that the Brickgao covers the distance between any two points in the time equal to the squared length of the segment between the points. It is also known that initially the coordinates of the Brickgao and the goal building are the same. You are asked to find such an order of bricks, that the Brickgao could move all the bricks to the building in a minimum time period. You can assume the no two bricks shared the same coordinates. If more than one optimum moving sequence Brickgao could find, he would choose the smallest lexicographic one because of the inherent sense of order.