0850. Rectangle Area II¶
题目信息¶
- 题号:
0850
- 难度:
Hard
- 主题:
几何、矩形并集、面积
- 原题:
- 重点:
求所有轴对齐矩形覆盖区域的并集面积,重叠部分只能计算一次;最终结果对 10^9+7 取模
题目重述¶
给定若干与坐标轴平行的矩形,rectangles[i] = [x1, y1, x2, y2] 表示左下角 (x1, y1) 和右上角 (x2, y2),并保证每个矩形宽、高均为正。
请计算至少被一个矩形覆盖的平面区域总面积。多个矩形的重叠部分只能计入一次,边界本身没有面积。由于结果可能很大,返回面积对 10^9 + 7 取模后的值。
1 <= rectangles.length <= 200,每项恰好包含四个坐标;所有坐标在 [0, 10^9] 范围内,每个矩形面积非零。
自建示例¶
两个矩形部分重叠:
输入:rectangles = [[0,0,2,2],[1,1,3,3]]
输出:7
解释:两个矩形面积各为 4,交叠的 1×1 区域面积为 1,因此并集面积为 4 + 4 - 1 = 7。
只有一个单位矩形:
输入:rectangles = [[5,7,6,8]]
输出:1
解释:矩形数量达到题目允许的最小值,唯一矩形宽和高都为 1,没有重叠需要去重,因此并集面积为 1。