Upside-Down

shep_com Criterion 2021 Round 14
Limits 1.5s, 512 MB

In this problem, you are given a tetrahedron in 33-dimensional space. A tetrahedron is defined as “a solid having four plane triangular faces; a triangular pyramid.” You are given the coordinates of 4 vertices of a tetrahedron in 33-dimensional space. It is guaranteed that the first 33 out of 44 of these points are situated in a plane parallel to the XYXY plane. Let’s call this plane the base of the tetrahedron. Let’s call the 4th point the apex of this tetrahedron. It is also guaranteed that the center of mass of this tetrahedron is the origin of this coordinate system.

Now, let’s go through some steps to transform this tetrahedron:

  • Mirror the tetrahedron with respect to the XYXY plane. Mirroring a point PP with respect to a plane in 3d space will generate a new point PP’ such that the plane bisects the straight line PPPP’ and the line PPPP’ is perpendicular to the plane. For example, mirroring the point A(1,2,3)A(1,2,3) with respect to the XYXY plane gives a new point A(1,2,3)A’(1,2,-3). The straight-line AAAA’ is bisected by the XYXY plane at (1,2,0)(1,2,0) and the line AAAA’ is perpendicular on the XYXY plane.

  • After mirroring, multiply each coordinate with a factor kk. This will effectively scale the tetrahedron by this factor kk.

  • Now, translate the transformed and scaled tetrahedron only along the ZZ-axis (the XX and YY coordinates remain unchanged) so that the new position of the apex point is in the same plane containing the original base plane. ( In Euclidean geometry, a translation is a transformation that moves every point of a shape by the same distance in a given direction)

Now, depending on the value of kk the transformed tetrahedron might or might not fit inside the original tetrahedron. If none of the points of the transformed tetrahedron is situated outside the original tetrahedron, then it is said that the transformed tetrahedron fits perfectly inside the original tetrahedron. On the other hand, if even a single point of the transformed tetrahedron is situated outside the original tetrahedron, then it cannot be said to perfectly fit inside. Your job is to find the biggest value of kk for which the transformed tetrahedron fits perfectly inside the original tetrahedron. Notice it is possible that after applying the necessary transformations, the modified tetrahedron will never fit inside the original tetrahedron. In this case, the value of k will be 0.

Input

The input will start with an integer TT (1T1000001\leq T\leq 100000), which stands for the number of test cases.

This will be followed by TT test cases. Each test case will have 44 lines describing the 44 vertices of a tetrahedron. Each line contains 33 space-separated real numbers ai,bi,cia_i, b_i, c_i (10000ai,bi,ci10000)(-10000\leq a_i, b_i, c_i\leq 10000) corresponding to the XX, YY, and ZZ-axis coordinates of that vertex.

You can safely assume that the input tetrahedron will be non-degenerate (the volume will never be 0).

Output

For each test case, print the value of the scaling factor kk, in a newline. Errors less than 10410^{-4} will be ignored.

Sample

InputOutput
2
3 3 -3
-1 -5 -3
-2 2 -3
0 0 9
3 3 -3
-2 -5 -3
-2 1 -3
1 1 9
0.5
0.4

Submit

Login to submit.

Statistics

67% Solution Ratio
aropanEarliest, 11M ago
aropanFastest, 0.5s
aropanLightest, 1.0 MB
BigBagShortest, 2886B
Toph uses cookies. By continuing you agree to our Cookie Policy.