2021牛客暑期多校训练营6 H. Hopping Rabbit(扫描线)

Description

一只兔子在草原上跳来跳去,草原上有猎人布下的n个陷阱.现在将草原看作一个二维直角坐标系,兔子看作一个点,陷阱看作一个矩阵(且它的边必定与x轴或y轴平行),兔子每次会沿x轴或y轴方向移动距离d(即如果兔子在,它跳一次后在四个点中的一个.问在坐标系中是否存在一个点,使兔子无论怎么跳都不会掉进陷阱.

Solution

扫描线裸题，由于兔子的运动具有周期性，只能在 上，不妨把所有矩形都平移到 的平面上，然后利用扫描线对每个 进行扫描，如果存在一个 ，在这一行中有点没有被覆盖，那么就可以选取这个点。
以下图来自官方题解，如图所示：


注意到有一些矩形可能很大，或者可能在平移的时候被分割成多个矩形，分类讨论一下就可以了， 方向上可能被截成两部分， 方向同理，于是最多会被分成4个矩形。
剩下的就需要学习扫描线，使用线段树进行区间修改，区间查询即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48499549