Editorial for DMPG '19 B5 - Triangles

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.

Author: r3mark

Consider a triangle whose vertices have x-coordinates x_1, x_2, x_3 where x_1 \le x_2 \le x_3. Note that if a point is contained in the interior of this triangle, then its x-coordinate must be between x_1 and x_3. Say we sort the points by their x-coordinate. By the observation, if we form a triangle by three consecutive points after sorting, then it is guaranteed that no other point will be inside this triangle. The problem then reduces to finding three consecutive points which have at least one red and one blue point. Such a triplet exists if and only if there is at least one point of each colour. The triplet can easily be found since there are only \mathcal{O}(N) to check.

Time Complexity: \mathcal{O}(N \log N)

Comments


  • -1
    discoverMe  commented on April 30, 2019, 2:02 a.m. ← edit 3

    nvm if there is at least 1 point of each color you can find a solution


    • -1
      subscriber  commented on April 30, 2019, 12:44 p.m. ← edit 2

      That was what I considered but this works as well but very tricky to spot lawl


  • 6
    Robbinb1993  commented on April 27, 2019, 12:14 p.m. ← edit 2

    I took any blue and red point (if they exist) and then found the other point such that the area of the triangle formed is minimal. This way the complexity is just \mathcal{O}(N). If there would be another point inside the triangle formed of minimal size, we could have created a triangle of smaller area by using this point as the third point. But if this was the case, the triangle obtained of minimal area size is not minimal (contradiction). So there cannot be another point inside the triangle of minimal area.