Editorial for Wesley's Anger Contest 2 Problem 4 - The Ninth Triangle of the Underworld


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.

Authors: wleung_bvg

This problem is asking you to minimize the area of the union of two triangles given that you can translate the triangles to any location, and you can reflect the triangles, with the added restriction that one side of one triangle must lie on the same line as one side of the other triangle. Finding the area of the union of two triangles is equivalent to finding the area of the intersection subtracted from the total area of the two triangle separately.

Since there are only 18 possible orientations for the pairs of triangles, we can try them all. If we observe the area of the intersection as a function of the horizonal displacement between the two triangles (assuming the two bases are parallel to the x-axis), then we can see that this function is unimodal, allowing us to ternary search for the answer. The area of the intersection of two (fixed) triangles can be found with a variety of methods, most involving line intersections. One such algorithm that uses line intersections is the Sutherland-Hodgman polygon clipping algorithm.

Special care should be taken to ensure that floating point calculations are done accurately.

Time Complexity: \mathcal{O}(\log({\max{\{a, b, c, d, e, f\}}}))


Comments


  • -5
    failed_coder  commented on Nov. 3, 2019, 1:21 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.