ACM ICPC World Finals 2010

Problem K: Paperweight

With a basic familiarity with geometry, this problem is relatively straight forward, though there is one notable pitfall. The general idea is to simply try all C(5, 3) = 10 possible triples of points that can form the base plane of the paper weight, and for each such weight check whether it is valid and then check the distance of the led from that plane.

To check whether a position is valid, one needs to verify that no part of the paperweight lies below the chosen base plane, and that the center of mass, when projected onto the base plane, lies inside the base plane within a margin of 0.2 units. In this part we find what is probably the most tricky case: it can happen that a fourth point of the tetrahedron lies in the base plane, meaning that the projection of the center of mass should lie in the convex hull of the four points that lie in the base plane.