# Practice on Toph

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

# Upside-Down

By shep_com · Limits 1.5s, 512 MB

In this problem, you are given a tetrahedron in $3$-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 $3$-dimensional space. It is guaranteed that the first $3$ out of $4$ of these points are situated in a plane parallel to the $XY$ 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 $XY$ plane. Mirroring a point $P$ with respect to a plane in 3d space will generate a new point $P’$ such that the plane bisects the straight line $PP’$ and the line $PP’$ is perpendicular to the plane. For example, mirroring the point $A(1,2,3)$ with respect to the $XY$ plane gives a new point $A’(1,2,-3)$. The straight-line $AA’$ is bisected by the $XY$ plane at $(1,2,0)$ and the line $AA’$ is perpendicular on the $XY$ plane.

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

• Now, translate the transformed and scaled tetrahedron only along the $Z$-axis (the $X$ and $Y$ 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 $k$ 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 $k$ 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 $T$ ($1\leq T\leq 100000$), which stands for the number of test cases.

This will be followed by $T$ test cases. Each test case will have $4$ lines describing the $4$ vertices of a tetrahedron. Each line contains $3$ space-separated real numbers $a_i, b_i, c_i$ $(-10000\leq a_i, b_i, c_i\leq 10000)$ corresponding to the $X$, $Y$, and $Z$-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 $k$, in a newline. Errors less than $10^{-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


### Statistics

67% Solution Ratio

aropanEarliest, 3w ago

aropanFastest, 0.5s

aropanLightest, 1.0 MB

BigBagShortest, 2886B