Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Minimizing Sphere

Limits: 20s, 512 MB

You will be given some points in a 3D co-ordinate system. You have to find the minimum volume of the sphere which can enclose all of the points.

Input

The first line of the input contains the number of testcases T (0 < T ≤ 20). Each test case begins with an integer N (1 < N ≤ 55). Next N line each contains three integers representing the x, y, z co-ordinates of the points. Absolute value of all co-ordinates lie between 0 to 100.

Output

For each case print the minimum volume of the sphere. Errors less than 10-4 will be ignored.

Samples

InputOutput
2
3
1 2 3
5 -2 3
9 5 -12
2
1 0 0
5 21 -11
2757.47031865
7275.96129172

Author
  • forthright48's Avatar

    forthright48

    Samiul is a student at North South University and a part-time Software Engineer at Mukto Software Ltd. Sport programming is one of his hobbies. He loves reading manga - One Piece being his favorite.
Discussion
Submit

Login to submit