《清理海报》题目分析

为了方便描述，我们假设N张海报按照张贴的顺序依次是P1, P2, ... PN。 本题的重点在于通过海报的位置、大小，求出：

1. 哪些海报4个角都都被覆盖住了，这些海报不能被小Hi选为一开始撕的海报
2. 有哪些对海报(Pa, Pb)之间是存在直接覆盖关系的，也就是撕掉Pa导致Pb被撕掉

如果我们能求出以上信息，我们就可以构造如上图所示的DAG（有向无环图）。每一个节点代表一张海报，Pa和Pb之间存在一条有向边(Pa, Pb)当且仅当Pa被Pb覆盖。

对于每一个节点Pi，我们可以通过搜索得到Pi能到达的所有节点，这些节点就是撕掉Pi会连带撕下的海报。

而通过海报的位置、大小求出我们需要的两类信息，本质上是两个简单的计算几何问题： 1. 判断两个矩形是不是相交（有大于0的公共面积）
2. 判断一个点是不是在矩形内

其中判断一个点是不是在矩形内很简单，我们不在赘述。

判断两个矩形是不是相交需要有一点技巧。如果直接判断什么情况下相交，我们会发现需要讨论很多种情况：

如果我们逆向思维，判断什么情况下不相交，我们会发现实际只有两种情况，局面豁然开朗：
1. 两个矩形在X方向上是相离的
2. 两个矩形在Y方向上是相离的

于是我们判断Pi和Pj是不是相交可以很简单的实现：

bool overlap(int i, int j) { 
    return !(x1[i] >= x2[j] || x1[j] >= x2[i] 
         || y1[i] >= y2[j] || y1[j] >= y2[i]);
}