Mission Impossible

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

There are A, B, C, D four kinds of resources, A can be obtained at any point in the X-axis. B can be obtained at any point in the Y-axis. C and D each will only be able to achieve at a certain point. Giving the coordinates of C and D, the coordinates of your current location. Find the shortest path to obtain the four kinds of resources and go back.

Input

The first line contains the number T of test cases(T<=150). Each of the following T lines consists of six integers cx, cy, dx, dy, hx and hy. (cx, cy) is the coordinates of resource C, (dx, dy) is the coordinates of resource D, (hx, hy) is the coordinates of your current location.
All the numbers of the input are in the range [-1000, 1000].

Output

Your program should produce a single line for each test case containing the length of the shortest path. The answers should be rounded to two digits after the decimal point.

Sample Input

3 1 1 2 2 3 3 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1

Sample Output

8.49 5.66 6.83

Hint

chenheng

Source

HDOJ Monthly Contest – 2010.01.02

提交代码