F - Rectilinear Polygons Editorial by en_translator
Hint
Did you consider \(N = 1\)?
Generally, when choosing a solution, it is necessary that it solves the problem with weaker constraints.
Solution
Let’s first consider \(N=1\).
We scan in the increasing order of \(x\) and manage if each \(y\) coordinate is included in the polygon.
We only focus on those edges of the polygon parallel to the \(y\) axis, and inspect them in the increasing order of their \(x\) coordinates.
For any edge with endpoints \((X, Y_1)\) and \((X, Y_2) (Y_1 \lt Y_2)\), this edge flips the parity of whether or not the segment \([Y_1,Y_2]\) is included in the polygon.
Moreover, since the polygon is simple, we can prove that never is it possible that some points of \([Y_1,Y_2]\) is inside the polynomial while some points are outside.
Thus, if an arbitrary point in \([Y_1,Y_2]\) was included in the interior of the polygon, then by the focused edge the entire \([Y_1,Y_2]\) will become outside the polygon.
Conversely, if a point in \([Y_1,Y_2]\) was not included in the polygon, then the entire \([Y_1,Y_2]\) will become inside the polygon.
Therefore, if we can process “add \(1\) to a segment”, “add \(-1\) to a segment”, and “get the value of a point” fast, then we can manage whether the points of each \(y\) coordinate is included in the polygon.
Such operations can be implemented with a segment tree with lazy propagation (Lazy Segtree in ACL).
Now let us consider general \(N\).
First, we perform the operations described above for each polygon in order to classify the edges (parallel to the \(y\) axis) into two kinds.
In order to answer the question, it is sufficient to manage, for each point of each \(y\) coordinate, how many polygons include the point; this can be accomplished by performing “add \(1\) to a segment”, “add \(-1\) to a segment”, and “get the value of a point” fast, just like before.
Hence, we could solve the problem by sorting the off-line queries and the edges (parallel to the \(y\) axis) in the increasing order of \(x\) coordinates.
posted:
last update: