Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3968
Final Defense Line

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

There is a circle in the plane. Both the coordinates of the center and the radius are unknown.

Chiaki found three distinct points A, B and C in the plane. And she also knows the shortest distance from each point to the circumference.

Chiaki would like to find the smallest circle according to above information.

Note that in general, a circle with infinite radius is a line. But in this problem, line is not considered as a circle.


There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 2 × 105), indicating the number of test cases. For each test case:

The first line contains three integers xa, ya and da (-100 ≤ xa ≤ 100, ya = 0, 1 ≤ da ≤ 100) denoting the coordinates of A and the shortest distance to the circumference.

The second line contains three integers xb, yb and db (-100 ≤ xb ≤ 100, yb = 0, 1 ≤ db ≤ 100) denoting the coordinates of B and the shortest distance to the circumference.

The third line contains three integers xc, yc and dc (-100 ≤ xc, yc, dc ≤ 100, dc ≠ 0) denoting the coordinates of C and the shortest distance to the circumference.

If the distance is equal to 0, the point is on the circumference. If distance is greater than 0, the point is inside the circle. If distance is less than 0, the point is outside the circle and the shortest distance is the absolute value.

It is guaranteed that the minimum possible radius of the circle is at most 104.


For each test case, if there are infinite possible circles, output -1 in a single line. If there is no such circle, output 0 in a single line. Otherwise, output an integer m and a real number r in a single line separated by one space denoting the number of possible circles and the radius of the smallest circle. You answer will be accepted if the relative error of your answer is no more than 10-6.

Sample Input

0 0 1
3 0 2
10 2 2
0 0 1
3 0 2
10 2 -2

Sample Output

2 10.327329213474
2 5.341730785446


The image below shows the sample.

Author: LIN, Xi
Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status