Editorial for DMOPC '21 Contest 1 P5 - Perfect Cross


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

Subtask 1

First of all, we should rotate the points and queries by 45^{\circ}. This can be done in both directions, so that the problem is reduced to finding the pair of points which form the steepest line for both lines of the cross. Now, we observe that after sorting the points by x, the steepest pair of points must be adjacent in the list of points. We can use this fact to brute force on the set of points for each query.

Time Complexity: \mathcal{O}(NQ)

Subtask 2

Let's see if we can extend the observation above to apply to the full solution. We should note that after rotation, the range of points which lie within S steps from a query location forms an axis-aligned square of length 2S. This should inspire us to perform a line sweep on y. Specifically, we maintain a sweeping window of points with width 2S, adding and removing points as they enter and leave the window. Whenever a query aligns with the window, we need to find the steepest pair of points in a certain range. This calls for range queries and point updates, which we can support using a segment tree.

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


Comments

There are no comments at the moment.