0223. Rectangle Area
====================
题目信息
--------
:题号: 0223. 矩形面积
:难度: Medium
:主题: 几何、矩形、区间交集、容斥
:原题: `LeetCode 0223 `_
:重点: 轴对齐矩形的覆盖并集、一维投影求交、边界接触没有面积
题目重述
--------
平面上有两个边与坐标轴平行的矩形。第一个矩形由左下角 ``(ax1, ay1)`` 和右上角
``(ax2, ay2)`` 给出,第二个矩形由左下角 ``(bx1, by1)`` 和右上角 ``(bx2, by2)`` 给出。
返回它们覆盖区域的并集面积:被至少一个矩形盖住的平面只计算一次。
坐标均为整数,并满足 ``-10^4 <= ax1 <= ax2 <= 10^4``,另外三组坐标同样如此。因此每个矩形
的左边不晚于右边、下边不晚于上边,但允许宽或高为 0。矩形可以分离、部分重叠、完全包含,
也可以只在边或顶点处接触。题目返回覆盖面积,不要求输出重叠矩形的坐标;八个参数按值传入,
不存在需要修改的输入结构。
由约束可知单个矩形面积至多 ``2 \times 10^4 \times 2 \times 10^4 = 4 \times 10^8``,两个面积
之和不超过 ``8 \times 10^8``,结果落在 32 位有符号整数范围内。
自建示例
--------
部分重叠:
.. code-block:: text
输入:ax1=-1, ay1=0, ax2=3, ay2=4, bx1=1, by1=2, bx2=5, by2=5
输出:24
解释:面积分别为 16 和 12;重叠区域宽 2、高 2、面积 4,并集为 16 + 12 - 4 = 24。
一个矩形完全落在另一个内部:
.. code-block:: text
输入:ax1=0, ay1=0, ax2=4, ay2=4, bx1=1, by1=1, bx2=3, by2=2
输出:16
解释:内矩形面积 2 已经包含在外矩形的 16 中,并集仍是 16。
只在竖直边上接触:
.. code-block:: text
输入:ax1=0, ay1=0, ax2=2, ay2=3, bx1=2, by1=1, bx2=4, by2=4
输出:12
解释:公共部分是 x=2 上的一段线段,没有二维面积,总面积为 6 + 6。
退化矩形:
.. code-block:: text
输入:ax1=2, ay1=0, ax2=2, ay2=5, bx1=0, by1=1, bx2=4, by2=3
输出:8
解释:第一个矩形左右边重合,面积为 0;并集等于第二个矩形的面积 8。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
return unionByInclusionExclusion(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
}
private:
int countCoveredUnitSquares(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
const int left = std::min(ax1, bx1);
const int right = std::max(ax2, bx2);
const int bottom = std::min(ay1, by1);
const int top = std::max(ay2, by2);
int area = 0;
for (int x = left; x < right; ++x) {
for (int y = bottom; y < top; ++y) {
const bool in_a = x >= ax1 && x < ax2 && y >= ay1 && y < ay2;
const bool in_b = x >= bx1 && x < bx2 && y >= by1 && y < by2;
if (in_a || in_b) {
++area;
}
}
}
return area;
}
int unionByInclusionExclusion(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
const long long area_a = static_cast(ax2 - ax1) * (ay2 - ay1);
const long long area_b = static_cast(bx2 - bx1) * (by2 - by1);
const long long overlap_left = std::max(ax1, bx1);
const long long overlap_right = std::min(ax2, bx2);
const long long overlap_bottom = std::max(ay1, by1);
const long long overlap_top = std::min(ay2, by2);
const long long overlap_width = std::max(0LL, overlap_right - overlap_left);
const long long overlap_height = std::max(0LL, overlap_top - overlap_bottom);
return static_cast(area_a + area_b - overlap_width * overlap_height);
}
};
题解
----
覆盖区域的原始搜索空间
~~~~~~~~~~~~~~~~~~~~~~
坐标都是整数,轴对齐矩形 ``[x1, x2] \times [y1, y2]`` 的面积等于其中单位正方形的个数:每个
格子以整数点 ``(x, y)`` 为左下角,覆盖半开区域 ``[x, x+1) \times [y, y+1)``。并集面积就是
至少被一个矩形盖住的格子数量。
``countCoveredUnitSquares`` 取两个矩形的外接范围,枚举其中每个单位格子,判断左下角是否落在
A 或 B 的半开覆盖里。每个被覆盖格子恰好加 1,分离、包含、部分重叠和边界接触都不会漏计或
重复计:只接触边或点时,不存在同时满足 ``x < 右边界`` 且 ``x >= 左边界`` 的正宽度格子。
外接范围边长可达 ``2 \times 10^4``,双重循环最坏接近 ``4 \times 10^8`` 次判断。正确性来自
“逐格检查覆盖”,瓶颈也正是这层与面积同阶的枚举。真正重复的工作不是判断某个格子是否被盖住,
而是对整块连续矩形区域反复做同一种成员测试。
两次计入只发生在交集上
~~~~~~~~~~~~~~~~~~~~~~
每个矩形自身是连续块,面积可以直接用宽乘高得到,不必再数格子:
.. math::
area(A) = (ax2 - ax1)\,(ay2 - ay1), \quad
area(B) = (bx2 - bx1)\,(by2 - by1)
``area(A) + area(B)`` 已经覆盖全部格子,但交集中的格子被加了两次。容斥把并集改写成:
.. math::
area(A \cup B) = area(A) + area(B) - area(A \cap B)
于是问题从二维枚举收缩为:求出两个轴对齐矩形的交集面积。若能在常数时间内得到交集,格子循环
就可以整段删除。
投影求交代替分情况讨论
~~~~~~~~~~~~~~~~~~~~~~
两个轴对齐矩形的交集(若存在正面积)仍是轴对齐矩形。点 ``(x, y)`` 同时落在两个矩形内,当且
仅当 ``x`` 落在两个 ``x`` 投影的交集里,并且 ``y`` 落在两个 ``y`` 投影的交集里。一维闭区间
``[p, q]`` 与 ``[r, s]`` 的交是 ``[\max(p, r), \min(q, s)]``。因此:
.. code-block:: text
overlap_left = max(ax1, bx1)
overlap_right = min(ax2, bx2)
overlap_bottom = max(ay1, by1)
overlap_top = min(ay2, by2)
有效宽度为 ``max(0, overlap_right - overlap_left)``,高度同理。任一方向没有正长度,交集就
没有二维面积。这个公式统一处理分离、相切、部分重叠和包含,不再枚举几何关系。
未截断差值如何对应相交类型
~~~~~~~~~~~~~~~~~~~~~~~~~~
对部分重叠示例和另外两种边界,水平方向的未截断宽度分别为:
.. list-table::
:header-rows: 1
* - 情形
- 左、右端
- 未截断宽度
- 有效宽度
* - 部分重叠
- ``1, 3``
- ``2``
- ``2``
* - 包含
- ``1, 3``
- ``2``
- ``2``
* - 边接触
- ``2, 2``
- ``0``
- ``0``
* - 左右分离
- ``3, 1``
- ``-2``
- ``0``
分离时两个方向都可能得到负数。若先把两个负数相乘再当作重叠面积,会得到正值,容斥反而把并集
算大。必须先把每个方向截断到 ``0``,再相乘。边接触得到宽度 0,乘积仍为 0,与“线段没有面积”
一致。包含关系不需要单独分支:内矩形的投影已经是外矩形投影的子集,交集面积等于较小者。
代码分析
~~~~~~~~
``countCoveredUnitSquares`` 保留原始定义:外接框内每个单位格子检查一次覆盖。公共入口调用
``unionByInclusionExclusion``,它删除整层格子循环,只保留两个矩形面积和四个投影端点。
宽和高先转成 ``long long`` 再相乘,避免把乘法写在 ``int`` 里依赖约束碰巧不溢出。重叠端点
同样提升后再相减,使 ``overlap_right - overlap_left`` 在分离时保持正确的负号,随后被
``max(0, ·)`` 截断。主解不分配与坐标范围成正比的容器,也不修改调用参数。
复杂度与边界
~~~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要代价
* - 枚举单位格子
- ``O(WH)``
- ``O(1)``
- 扫描两个矩形外接范围中的每个单位格子
* - 容斥求并
- ``O(1)``
- ``O(1)``
- 两次面积计算和四个投影端点比较
``W``、``H`` 是外接范围的宽和高,最坏约为 ``2 \times 10^4``。宽或高为 0 时,对应面积为 0,
容斥公式仍然成立。两个矩形完全重合时,减去的交集等于其中一个面积,并集不会变成 0。输入坐标
允许为负,投影取最大左端和最小右端与符号无关。