BICYCLE - Bicycle

no tags 

Peter likes to go to school by bicycle. But going by bicycle on sidewalks is forbidden and going along roads is dangerous. That's why Peter travels only along special bicycle lanes. Fortunately Peter's home and school are in the immediate proximity of such paths. In the city where Peter lives there are only two bycycle lanes. Both lanes have the form of a circle. At the points where they cross it is possible to move from one path to the other. Peter knows the point where he enters the road and the point at which it is necessary to leave to enter the school. Peter is interested in the question: "What is the minimal distance he needs to cover along the lanes to get to school?"

Input

t – the number of test cases [t<=100], then t test cases follow.
The first 2 lines of each test case contain the description of the bicycle lanes:
x1 y1 r1 - 3 integers (x1, y1 - coordinates of the center of the 1st circle, r1 - radius of 1st circle)
x2 y2 r2 - 3 integers (x2, y2 - coordinates of the center of the 2nd circle, r2 - radius of 2nd circle)
-200 <= x1, x2, y1, y2 <= 200
0 <= r1, r2 <= 200
Next 2 lines contain the coordinates of Peter's home and school:
px1, py1 - 2 real numbers
px2, py2 - 2 real numbers

You may assume that this points lie on the circle with high accuracy (10-8). Both points may lie on the same circle.

Output

For each test case output the minimum distance that Peter needs to go from home to get to school. The precision of the answer must be under 0.0001. If it's impossible to get to school using the bicycle lanes output -1.

Example

Input:
3

0 0 5
4 0 3
3.0 4.0
1.878679656440357 -2.121320343559643

0 0 5
4 0 3
4.0 3.0
4.0 -3.0

0 0 4
10 0 4
4.0 0.0
6.0 0.0

Output:
8.4875540166
6.4350110879
-1
Illustration of sample test data

hide comments
tld: 2010-04-11 09:17:18

I want to know if two circles coincide whether peter can go to school? Distance/-1

Last edit: 2010-04-11 09:17:41
[Rampage] Blue.Mary: 2009-12-26 16:47:14

There are test cases in which two circles coincide.

:D: 2009-07-31 20:02:52

Can anyone tell me why are there so many WA to this problem, also from top users. Is there some I/O issue?


Added by:Roman Sol
Date:2005-01-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:5th Russian National Command Olympiad for schoolboys in programming