hiho一下第140周《清理海报》题目分析

6
1

《清理海报》题目分析

为了方便描述,我们假设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]);
}

3 answer(s)

0

示例构造的DAG图中,为何(3,4)没有连线,而是(1,4)有连线?

  • (1,4)有连线,(3,4)应该也有连线

  • (3,4) 应该有

  • 添加评论
  • reply
0

赞赞赞

0

很强!!

write answer 切换为英文 切换为中文


转发分享