Sphere Set

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Recently I solved several geometry problem about sphere in SPOJ, and it's really good. After that, I came up with and idea: given N spheres in the space, calculate the volume of intersection of them.
When I finish the stardard program and make the random dataset, I found that almost all data would output "0". Obviously, it's an experience of failure! But I really did not want to give up this valuable idea, so I dicided to construct some data whose answer is not "0".
My construction algorithm is described like this:
1. Get N points in the space randomly and assign a equivalent radius to each of them. We can get a initial data.
2. Run my stardard program using the current data. If the answer is 0, expand all the radius equivalently and continue the step 2; otherwise, finish the construction.
I successfully constructed several data whose answer is not "0" using the algorithm described above.
During the construction process, I found another funny algorithm problem: for the given N points in the space, what is the minimum radius we can assign to each sphere so that the volume of intersection of them is large than 0.

Input

The first line of input file contains an integer T indicating the number of case.
In each test case:
The first line contains an integer N(2 <= N <= 100).
The next N lines each line contains three integers x, y, z indicating the coordinate of an point in the space. (1 <= x <= 100)

Output

For each test case:
Output a float number indicating the answer which should accurate to two decimal places.

Sample Input

2
4
10 10 10
20 10 10
20 20 10
10 20 10
4
10 10 10
10 50 50
50 10 50
50 50 10

Sample Output

7.07
34.64

Source

dut200901102

Manager

Information
Solved Number6
Submit Number54
Problem Tags
geometry
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel