Editorial for UTS Open '15 #6 - Tetrahedra


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Let's solve each face separately, taking the base area of the face and subtracting the area of the portion of the face which lies inside the other tetrahedron.

Suppose our face is defined by the points A, B, C. The base area is:

\displaystyle \dfrac{|\overrightarrow{AB}\times\overrightarrow{AC}|} 2

The face lies on the plane P defined by the point A and the normal vector \overrightarrow{n}:

\displaystyle \overrightarrow{n}=\dfrac{\overrightarrow{AB}\times\overrightarrow{AC}}{|\overrightarrow{AB}\times\overrightarrow{AC}|}

(Editor's note: the paragraphs about getting the enclosed area might be bullshit)

To find the area of the portion enclosed by the other tetrahedron, consider every pair of points X and Y from the other tetrahedron. If they lie on opposite sides of P (that is, sgn(\overrightarrow{AX}\cdot\overrightarrow{n})\ne sgn(\overrightarrow{AY}\cdot\overrightarrow{n}), project the line \overline{XY} onto P and add the projection to the set of points S.

Since A, B, C, and the members of S all lie on P, we can redefine each point to make the problem 2D. Define \overrightarrow{x} and \overrightarrow{y} as follows:

\displaystyle \overrightarrow{x}=\dfrac{\overrightarrow{AB}}{|\overrightarrow{AB}|}

\displaystyle \overrightarrow{y}=\overrightarrow{x}\times\overrightarrow{n}

Then, for a point Q, its new x-coordinate is \overrightarrow{AQ}\cdot\overrightarrow{x} and its new y-coordinate is \overrightarrow{AQ}\cdot\overrightarrow{y}.

The intersection of the projection S and the triangle ABC is a polygon defined by every point Q such that:

  • Q \in S and Q is inside ABC, or
  • Q \in \{A,B,C\} and Q is inside S, or
  • Q is at the intersection of the border of ABC and the border of S

We can find the area of this polygon with the Shoelace Theorem. Subtract it from the base area calculated above to find your answer.

Complexity: \mathcal{O}(1)


Comments

There are no comments at the moment.