223. 矩形面积

🟠   🔖  几何 数学  🔗 力扣 LeetCode

题目

Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).

Example 1:


Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2

Output: 45

Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2

Output: 16

Constraints:

• -10^4 <= ax1 <= ax2 <= 10^4
• -10^4 <= ay1 <= ay2 <= 10^4
• -10^4 <= bx1 <= bx2 <= 10^4
• -10^4 <= by1 <= by2 <= 10^4

题目大意

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

• 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
• 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例 1：


输入： ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2

输出： 45

示例 2：

输入： ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2

输出： 16

提示：

• -10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4

解题思路

1. 矩形的面积计算：

   • 给定矩形的左下角和右上角的坐标，矩形面积可以用公式：

     Area = (右上角的x坐标 - 左下角的x坐标) * (右上角的y坐标 - 左下角的y坐标)

2. 判断重叠区域：

   • 两个矩形如果有重叠，那么重叠区域也可以看作一个矩形。需要计算这个重叠矩形的左下角和右上角坐标：
     • 左下角的 x 坐标：两个矩形左下角 x 坐标的较大值 overlapX1 = max(ax1, bx1) 。
     • 左下角的 y 坐标：两个矩形左下角 y 坐标的较大值 overlapY1 = max(ay1, by1) 。
     • 右上角的 x 坐标：两个矩形右上角 x 坐标的较小值 overlapX2 = min(ax2, bx2) 。
     • 右上角的 y 坐标：两个矩形右上角 y 坐标的较小值 overlapY2 = min(ay2, by2) 。

3. 重叠面积计算：

   • 如果重叠矩形的宽度和高度都大于 0，才有重叠面积：

     OverlapArea = (overlapX2 - overlapX1) * (overlapY2 - overlapY1)

   • 否则，重叠面积为 0。

4. 总面积计算：

   • 两个矩形的总面积等于各自面积之和减去重叠部分的面积：

     TotalArea = Area1 + Area2 - OverlapArea

复杂度分析

• 时间复杂度：O(1)，所有操作都是常数时间的计算。
• 空间复杂度：O(1)，只使用了几个额外变量。

代码

/**
 * @param {number} ax1
 * @param {number} ay1
 * @param {number} ax2
 * @param {number} ay2
 * @param {number} bx1
 * @param {number} by1
 * @param {number} bx2
 * @param {number} by2
 * @return {number}
 */
var computeArea = function (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
	// 重叠矩形的边界
	const overlapX1 = Math.max(ax1, bx1);
	const overlapX2 = Math.min(ax2, bx2);
	const overlapY1 = Math.max(ay1, by1);
	const overlapY2 = Math.min(ay2, by2);

	// 计算重叠面积
	let overlap = 0;
	if (overlapX1 < overlapX2 && overlapY1 < overlapY2) {
		overlap = (overlapX2 - overlapX1) * (overlapY2 - overlapY1);
	}

	// 计算两个矩形的面积
	const area1 = (ax2 - ax1) * (ay2 - ay1);
	const area2 = (bx2 - bx1) * (by2 - by1);

	// 总面积
	return area1 + area2 - overlap;
};

相关题目

题号	标题	题解	标签	难度	力扣
836	矩形重叠	[✓]	几何 数学	🟢	🀄️ 🔗
3025	人员站位的方案数 I		几何 数组 数学 2+	🟠	🀄️ 🔗
3027	人员站位的方案数 II		几何 数组 数学 2+	🔴	🀄️ 🔗
3047	求交集区域内的最大正方形面积		几何 数组 数学	🟠	🀄️ 🔗