矩形相交的面积 - 华为OD机试真题(JavaScript题解)

华为OD机试题库《C++》限时优惠 9.9

华为OD机试题库《Python》限时优惠 9.9

华为OD机试题库《JavaScript》限时优惠 9.9

针对刷题难，效率慢，我们提供一对一算法辅导， 针对个人情况定制化的提高计划（全称1V1效率更高）。

看不懂有疑问需要答疑辅导欢迎私VX： code5bug

题目描述

给出3组点坐标(x,y,w,h)，-1000<x,y<1000，w,h为正整数。

(x,y,w,h)表示平面直角坐标系中的一个矩形:

x,y为矩形左上角坐标点，向右w，向下h。

(x,y,w,h)表示x轴(x,x+w)和y轴(y,y-h)围成的矩形区域

(0,0,2,2)表示x轴(0,2)和y轴(0,-2)围成的矩形区域:

(3,5,4,6)表示x轴(3,7)和y轴(5,-1)围成的矩形区域

求3组坐标构成的矩形区域重合部分的面积。

输入描述

3行输入分别为3个矩形的位置，分别代表“左上角x坐标”，“左上角y坐标”，“矩形宽”，“矩形高” -1000 <= x,y < 1000

输出描述

输出3个矩形相交的面积，不相交的输出0。

示例1

输入：
1 6 4 4
3 5 3 4
0 3 7 3

输出：
2

题解

这道题目属于计算几何和矩形重叠问题。具体来说，它要求计算三个矩形的重叠部分的面积。这涉及到矩形之间的交集计算，属于基本的几何问题。

解题思路

要计算三个矩形的重叠面积，可以按照以下步骤进行：

1. 理解矩形表示：每个矩形由左上角坐标 (x, y)、宽度 w 和高度 h 表示。矩形的范围在 x 轴上是 [x, x + w)，在 y 轴上是 [y - h, y)。
2. 计算三个矩形的交集：
   • 交集的左边界是三个矩形右边界的最大值（即 max(x1, x2, x3)）。
   • 交集的右边界是三个矩形右边界的最小值（即 min(x1 + w1, x2 + w2, x3 + w3)）。
   • 交集的上边界是三个矩形上边界的最小值（即 min(y1, y2, y3)）。
   • 交集的下边界是三个矩形下边界的最大值（即 max(y1 - h1, y2 - h2, y3 - h3)）。
3. 判断交集是否存在：如果左边界小于右边界且下边界小于上边界，则交集存在；否则，交集面积为 0。
4. 计算交集面积：如果交集存在，面积为 (右边界 - 左边界) * (上边界 - 下边界)。

时间复杂度

• 读取输入的时间复杂度是 O(1)，因为输入是固定的三行。
• 计算边界和判断交集的时间复杂度是 O(1)，因为只有三个矩形。
• 总体时间复杂度是 O(1)。

空间复杂度

• 空间复杂度是 O(1)，因为只使用了固定数量的变量来存储矩形的参数和计算结果。

JavaScript

const rl = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout,
});

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

// Author: code5bug
(async () => {
    let [x1, y1, w1, h1] = (await readline()).split(' ').map(Number);
    let [x2, y2, w2, h2] = (await readline()).split(' ').map(Number);
    let [x3, y3, w3, h3] = (await readline()).split(' ').map(Number);

    // 如果有重叠的矩形区域，则重叠的矩形区域的四条边所在位置
    let top = Math.min(y1, y2, y3);
    let left = Math.max(x1, x2, x3);
    let bottom = Math.max(y1 - h1, y2 - h2, y3 - h3);
    let right = Math.min(x1 + w1, x2 + w2, x3 + w3);

    let area = 0;
    // 重叠的矩形存在
    if(left < right && bottom < top){
        // 计算面积
        area = (right - left) * (top - bottom);
    }
    console.log(area);

    rl.close();
})();

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏