当前位置：首页 > news >正文

华为OD机试_2025 B卷_矩形相交的面积（Python，100分）（附详细解题思路）

news 2025/7/1 17:35:05

题目描述

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

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

x, y为矩形左上角坐标点，w, h向右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 6 4 4
3 5 3 4
0 3 7 3

输出

2

说明
在这里插入图片描述

矩形重叠面积计算算法详解

核心解题思路

本题目要求计算三个矩形重合部分的面积。核心思路是通过分析矩形在x轴和y轴上的投影，确定三个矩形共同重叠的区域。解题步骤如下：

关键步骤

矩形坐标转换：
- 每个矩形由左上角坐标(x,y)、宽度w、高度h定义
- x轴投影：左边界x，右边界x + w
- y轴投影：由于坐标系向下为负，上边界y，下边界y - h
重叠区域确定：
- x轴重叠：取三个矩形左边界最大值作为重叠左边界，右边界最小值作为重叠右边界
- y轴重叠：取三个矩形上边界最小值作为重叠上边界，下边界最大值作为重叠下边界
- 重叠宽度：重叠右边界 - 重叠左边界
- 重叠高度：重叠上边界 - 重叠下边界
面积计算：
- 当重叠宽度和高度都为正时，面积 = 宽度 × 高度
- 否则面积为0

完整代码实现

def main():# 读取三个矩形的参数rects = []for _ in range(3):data = input().split()# 转换为浮点数处理（题目整数但为统一接口）x = float(data[0])y = float(data[1])w = float(data[2])h = float(data[3])rects.append((x, y, w, h))# 计算三个矩形的x轴重叠区域left_bound = max(rects[0][0], rects[1][0], rects[2][0])right_bound = min(rects[0][0] + rects[0][2], rects[1][0] + rects[1][2], rects[2][0] + rects[2][2])# 计算三个矩形的y轴重叠区域top_bound = min(rects[0][1], rects[1][1], rects[2][1])bottom_bound = max(rects[0][1] - rects[0][3],rects[1][1] - rects[1][3],rects[2][1] - rects[2][3])# 计算重叠区域的宽度和高度width = right_bound - left_boundheight = top_bound - bottom_bound# 计算重叠面积（当宽度和高度都为正时）if width > 0 and height > 0:area = width * heightelse:area = 0# 输出整数部分（题目要求整数）print(int(area))if __name__ == "__main__":main()

算法原理解析

1. 矩形投影原理

# 矩形在x轴投影：[x, x + w]
# 矩形在y轴投影：[y - h, y]

x轴：从左边界x到右边界x+w
y轴：从下边界y-h到上边界y（注意坐标系向下为负）

2. 重叠区域计算

# x轴重叠
left_bound = max(rect1_x, rect2_x, rect3_x)
right_bound = min(rect1_x + w1, rect2_x + w2, rect3_x + w3)# y轴重叠
top_bound = min(rect1_y, rect2_y, rect3_y)
bottom_bound = max(rect1_y - h1, rect2_y - h2, rect3_y - h3)

左边界：取三个矩形左边界最大值（最右边的左边界）
右边界：取三个矩形右边界最小值（最左边的右边界）
上边界：取三个矩形上边界最小值（最靠下的上边界）
下边界：取三个矩形下边界最大值（最靠上的下边界）

3. 面积计算逻辑

width = right_bound - left_bound
height = top_bound - bottom_bound
if width > 0 and height > 0:area = width * height
else:area = 0

有效性检查：宽度和高度必须为正才有重叠
整数输出：题目要求输出整数部分

示例解析

示例输入：

1 6 4 4
3 5 3 4
0 3 7 3

步骤解析：

矩形1：x=1, y=6, w=4, h=4
- x轴：[1, 5]
- y轴：[6-4, 6] = [2, 6]
矩形2：x=3, y=5, w=3, h=4
- x轴：[3, 6]
- y轴：[5-4, 5] = [1, 5]
矩形3：x=0, y=3, w=7, h=3
- x轴：[0, 7]
- y轴：[3-3, 3] = [0, 3]
重叠区域计算：
- x轴：左边界 = max(1, 3, 0) = 3
  右边界 = min(5, 6, 7) = 5
  宽度 = 5 - 3 = 2
- y轴：上边界 = min(6, 5, 3) = 3
  下边界 = max(2, 1, 0) = 2
  高度 = 3 - 2 = 1
面积：2 × 1 = 2

输出：2

边界情况测试

测试1：完全重叠

输入：
0 10 10 10
0 10 10 10
0 10 10 10计算：
x轴：max(0,0,0)=0, min(10,10,10)=10 → 宽度=10
y轴：min(10,10,10)=10, max(0,0,0)=0 → 高度=10
面积=100

测试2：部分重叠

输入：
1 5 4 5
2 6 4 4
3 4 5 6计算：
矩形1：x[1,5], y[0,5]
矩形2：x[2,6], y[2,6]
矩形3：x[3,8], y[-2,4]x轴：max(1,2,3)=3, min(5,6,8)=5 → 宽度=2
y轴：min(5,6,4)=4, max(0,2,-2)=2 → 高度=2
面积=4

测试3：无重叠

输入：
0 10 2 2
3 8 2 2
5 5 2 2计算：
x轴：max(0,3,5)=5, min(2,5,7)=2 （5>2）
宽度=2-5=-3 → 无效
面积=0

总结与扩展

关键知识点

矩形表示：理解坐标系中矩形的数学表示
投影分析：将二维问题分解为两个一维问题
边界计算：最大值最小值确定重叠区域
有效性检查：处理无重叠情况

扩展思考

非轴对齐矩形：

# 使用旋转矩阵处理旋转的矩形
def rotate_rect(rect, angle):# 计算旋转后的顶点# 使用分离轴定理检测重叠

三维空间重叠：

def clip_cuboids(cuboids):# 在x,y,z三个维度分别计算# 计算体积而非面积

部分重叠阈值：

def clip_with_threshold(rects, threshold=0.5):# 计算重叠面积与总面积的比例# 返回满足阈值的重叠区域

渐进式计算：

class OverlapCalculator:def __init__(self):self.left = -float('inf')self.right = float('inf')self.top = float('inf')self.bottom = -float('inf')def add_rect(self, x, y, w, h):self.left = max(self.left, x)self.right = min(self.right, x + w)self.top = min(self.top, y)self.bottom = max(self.bottom, y - h)return self.get_overlap()def get_overlap(self):width = self.right - self.leftheight = self.top - self.bottomif width > 0 and height > 0:return width * heightreturn 0