1038 - Picking Cabbage

1038. Picking Cabbage

时间限制 2000 ms 内存限制 32 MB

Once, Doraemon and Nobita planted a farm with cabbage. One night their farm was stealed by Takeshi Gian. Takeshi Gian picked away most of the cabbage, but left some cabbage in the farm. Then he left a note to Doraemon and Nobita, telling them the coordinate of the cabbage still in the farm. As soon as Doraemon and Nobita get the note, they run out to save their cabbage.

Doraemon has a warp gate in his house that can send them to a cabbage which they wanted to. Then they should run from one cabbage to another to get them. Since they wanted to get all the cabbage as soon as possible, they should run the shortest way. Can you calculate the shortest path that they should run

输入数据

There are multiple test cases. The first line is a positive integer stands for the number of test cases.

The first line of each test case is a positive integer N(1<=N<=15) stands for the number of cabbage that Takeshi Gian left.

Then N following lines each has two integer xi, yi, (0<=xi,yi<=100) stands for the coordinate of the cabbage.

输出数据

Output the shortest path of getting all the cabbage in one line keeping two decimal places.

Doraemon and Nobita just wanted to get all of the cabbage as soon as possible, so, don't bother about their path of getting back home.

样例输入

复制

2
3
0 0
0 1
0 2
3
0 0
0 1
1 0 \n
 \n
 · \n
 · \n
 · \n
 \n
 · \n
 · \n
 · \n

样例输出

复制

2.00
2.00    \n
    \n

提交

请先登录

提交