← All solutions

This was one of the most challenging problems. The problem has two components, both of which can be solved using a sweepline algorithm.

The first phase, to detect errors, can be done by finding intersections between all line segments defining the triangles (where you have to be careful not to count two segments belonging to the same triangle as an error). There is a standard, albeit somewhat complicated, algorithm for this.

The second phase, constructing the tree of contained triangles, can be done as follows: keep a list of all currently active triangles, sorted by the y coordinate of their bottommost edge. Note that this y coordinate changes as the sweepline moves from left to right, but the ordering of the currently active triangles determined by the y coordinate is invariant. The main observation is that, when adding a triangle, the parent of this triangle will be some ancestor of the triangle T immediately below it (where “below” is in the sense of the ordering described above). This ancestor can be found in O(log n) time.