ilovehinatashoyo's blog

Elegant solution for spoj TETRA

By ilovehinatashoyo, history, 6 years ago, In English

Hi,

I recently came across TETRA spoj problem and came to know that the solution of this problem is a formula (Which i dont have any idea on how was that derived). I was wondering if there is any other elegant way of solving this? like binary search over the answer or something like that? Any help would be appreciated.

ThankYou.

EDIT: would also be helpful if someone posts the derivation of the formula.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 15   Vote: I like it +7 Vote: I do not like it

The same problem exists in CodeChef as wall. An iterative numerical algorithm for finding the center and the radius of the sphere inscribed in an irregular Tetrahedron in terms of the lengths of the edges may exist. However, the formula based solution seems to be much more efficient.

To give you few hints about a simplified poof, suppose without loss of generality that XYZ is the base triangle of the tetrahedron, and that W is its top vertex. Suppose that the base triangle coincides with the xy-plane, and that its corners X, Y, and Z are located at (0, 0, 0), (xy, 0, 0), and (xz, yz, 0), respectively, where xy, xz, yz > 0. Then, it should be obvious that xy = XY, and that Pythagoras theorem can be used to derive expressions for xz and yz in terms of the edge lengths XY, YZ and ZX.

After finding the location of X, Y and Z, suppose that location of the top vertex W is (xw, yw, zw), where xw, yw, zw > 0. As the edge lengths WX, WY and WZ are known, the location of W should be the intersection point above the xy-plane of the three spheres whose centers are located at X, Y and Z, and whose radii are WX, WY, and WZ, respectively.

After finding the location of the top vertex W, suppose that the location of the center of the inscribed sphere C is (xc, yc, xc), where xc, yc, zc > 0, and that its radius is r. It should be obvious that zc = r, as the sphere has to be tangent to the tetrahedron base XYZ. It is possible to derive three expressions for the side faces of the tetrahedron WXY, WYZ and WZX, as each of them passes through three points with known locations. Suppose that the equation which describes each of these three faces is expressed as aix + biy + ciz + di = 0, where the four coefficients ai, bi, ci and di can be computed in terms of the locations of the three points that such face passes through. It is simple to show that the vector (ai, bi, ci) is normal to the face, and that the distance between C and such face can be expressed as |aixc + biyc + cizc + di| divided by the square root of (ai2 + bi2 + ci2). This gives three linear equations in three unknowns xc, yc and r provided that the absolute value ensures that the distance is always a positive value. The value of last unknown r is the required answer in each test case.

→ Reply