Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2335
Three Circles

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given the positions of three circles, you want to draw them on the paper with a pen. You can start drawing at any place and move the pen arbitrarily on the paper, the pen can be lifted or lowered at any time. If the pen is lifted up, you will draw nothing. You cannot draw partial circle, that means if you start drawing a circle, you must finish it, then you can draw another one.

It takes 1 unit time to move the pen a distance of 1 unit and 0 time to lift or lower the pen.

Your task is to calculate the minimum time to draw the three circles.


The input starts with a number T (T<=100) on the first line, which is the number of test cases. Each test case contains 9 real numbers in a line: x1 y1 r1 x2 y2 r2 x3 y3 r3

xi, yi(-10000 <= xi, yi <= 10000), ri(0 < ri <= 10000) is the coordinate of center and radius of the i-th circle.

Any two of the circles have no common points and it never happens that one circle is entirely inside another one.


For each test case, output the minimum time in a single line, the result is to be printed accurately rounded to three decimals.

Sample Input

0 0 0.5 -2 0 0.5 2 0 0.5
0 0 1 -2 2 1 2 2 1

Sample Output


Personal Homepage: http://student.zsu.edu.cn/~is02chs/

Author: CHEN, Shi
Source: ZOJ 3rd Anniversary Contest
Submit    Status