The Flowers Floating On The YueYa Lake

We all know the YueYa Lake of HDU. It is very beautiful, especially in the evening. However, most of HDU's ACMers may not know,because they only know where the apartments and the laboratory are and they often get lost when they go to other places even Canteen.

CR was very excited when he knew Spring Festival is Valentine's Day this year. Finally, that day is coming. He pulled out the map of HDU and then walked towards the direction of the YueYa Lake.He knew that today there would be a lot of beautiful MMs. Soon, he arrived and he was so lucky that he met a beautiful girl. The girl told him that she would like to have all the flowers floating on the water of YueYa Lake. She also told him if he fulfilled her this wish she was willing to be his girlfriend! How exciting!

Simply，we can see each of flowers as a point (Pi(xi, yi), 0<xi,yi, i≠j,xi≠xj) in the plane and CR stand at coordinate origin.CR must get all the flowers floating in the water and then go back to coordinate origin.Although our CR knew a little Kungfu of QingKung, it’s also a hard work, because it’s would cost CR |PiPj| calories of energy when he flew from Pi to Pj. Our small CR want to make it a wonderful thing that he spent the least energy. But there is a rule:

Before you reach the rightmost point , you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can visit Pj only when xj>xi. But when you reach the rightmost point, the rule has changed, you can only visit the points those have the smaller x-coordinate value than the point you are at now.For example, you are at Pi now, then you can visit Pj only when xj<xi.

Of course CR knew the answer, but what about you, clever ACMers?

Input consists of multiple test cases. Each case begins with a line containing a positive integer n(0 < n <= 500), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.
A test case with n = 0 terminates the input and this test case is not to be processed.

For each test case, your should output the least energy to finished the girl’s wish with the rule mentioned above. The answer should accurate up to 2 decimal places.

3
1 1
2 3
3 1
0

9.05

The path (0,0) - (3,1) - (2,3) - (1,1) - (0,0) makes the least energy.

西风萧瑟

HDU “Valentines Day” Open Programming Contest 2010-02-14