## 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 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 has negative or or lies above a certain line formed by connecting two points and . If any of these are true, the tree does not cover the point.

To check whether the point is above the line from to , we can use the slope-intercept form of the line (it has slope and y-intercept ). 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: