矩形交问题背公式

北文 · 2024-09-26 20:24:43 · 个人记录

给定若干矩形，计算每个矩形与多少个矩形有交 \mathcal O(n\log n)。
首先离散化就不说了。
考虑扫描线从下网上扫，先来看一张图，假设现在要统计与黑色矩形有交的矩形个数。

首先只有下边界与黑色矩形下边界有交的矩形才可能有贡献。 容易发现这五种矩形涵盖了所有矩形与黑色的关系，蓝色和橙色没贡献，不考虑。
我们把剩下的分为两类：
红色：上下边界位于黑色下边界两侧。
绿色/黄色：下边界在黑色下边界之上，在黑色上边界之下。
考虑统计红色的方案数：在扫下边界时加入线段，扫上边界删除线段，树状数组上查询与多少线段有交即可。
考虑统计绿色/黄色方案数：在扫下边界时加入线段，扫上边界时不做操作，树状数组上查询

容易发现这样能统计所有矩形。