Editorial for DMOPC '21 Contest 4 P1 - Tree Shopping

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: 4fecta

Let's fix a single tree and a single point to check if the tree covers the point. First, let's translate the figure so that (x_1, y_1) is at the origin. Then, reflect or rotate the diagram until the tree is entirely contained in the first quadrant. We've now reduced the problem to checking if a given point (x, y) has negative x or y or lies above a certain line formed by connecting two points (0, y_2) and (x_3, 0). If any of these are true, the tree does not cover the point.

To check whether the point is above the line from (0, y_2) to (x_3, 0), we can use the slope-intercept form of the line (it has slope -y_2/x_3 and y-intercept y_2). Take extra caution to avoid floating point arithmetic! Most solutions which employ floating point data types do not pass the first test case, which was specifically designed to hack imprecise solutions.

Time complexity: \mathcal{O}(NQ)


There are no comments at the moment.