华为OD机试经典题解：矩形相交面积计算与多语言实现

1. 项目概述与核心价值最近在技术社区和求职圈里“华为OD机试”的热度一直居高不下尤其是那些经典的算法真题几乎成了大家备考的“必刷题库”。今天要拆解的这道“矩形相交的面积”就是其中一道非常典型、也极具代表性的题目。它看似简单就是一个计算两个矩形重叠部分面积的问题但如果你真把它当成一道简单的几何题那可能就错过了它背后考察的算法思维和编程基本功。这道题频繁出现在华为OD的B卷乃至其他大厂的笔试中不是没有道理的。它完美地融合了基础的数学逻辑、严谨的边界条件判断以及对编程语言数据结构如坐标表示的熟练运用是检验一个程序员是否具备扎实基础和缜密思维的绝佳试金石。无论你是正在备战华为OD机考、校招笔试的应届生还是希望巩固算法基础的开发者这道题都值得你花时间深入研究。它不仅教你如何计算相交面积更重要的是它训练你如何将现实世界的几何问题抽象成计算机可以处理的逻辑和代码并在这个过程中规避掉所有可能的“坑”。接下来我会从问题本质、多种思路对比、到不同语言C、Java、Python、C、JS的具体实现与细节剖析为你呈现一份完整的“解题报告”。2. 问题本质与数学模型抽象2.1 问题重述与输入输出规范题目通常这样描述在二维平面直角坐标系中给定两个矩形的信息。每个矩形通过其左下角顶点坐标(x1, y1)和右上角顶点坐标(x2, y2)来确定。要求计算这两个矩形重叠部分的面积。如果两个矩形没有重叠则重叠面积为0。这是一个非常清晰的定义。关键在于我们需要从这8个数字两个矩形每个矩形两个点每个点两个坐标中推导出重叠矩形是否存在以及其大小。输入格式常见 一行或多行输入包含8个整数分别代表x1 y1 x2 y2 x3 y3 x4 y4其中(x1, y1)和(x2, y2)是第一个矩形的左下角和右上角坐标。(x3, y3)和(x4, y4)是第二个矩形的左下角和右上角坐标。 通常保证x1 x2,y1 y2,x3 x4,y3 y4即输入的坐标是有效的矩形。输出格式 一个整数表示相交部分的面积。2.2 核心数学模型投影与一维区间相交这是理解本题的关键。一个矩形在二维平面的相交可以分解为在两个独立维度X轴和Y轴上一维线段相交的问题。X轴投影将两个矩形投影到X轴上得到两个线段区间。矩形A:[x1, x2]矩形B:[x3, x4]Y轴投影将两个矩形投影到Y轴上得到两个线段区间。矩形A:[y1, y2]矩形B:[y3, y4]两个矩形相交当且仅当它们在X轴上的投影线段相交并且在Y轴上的投影线段相交。那么如何计算一维线段的相交长度呢 对于两个区间[a1, a2]和[b1, b2]假设a1 a2,b1 b2首先判断是否相交相交的条件是max(a1, b1) min(a2, b2)。如果这个条件不成立说明两个区间没有重叠部分。如果相交重叠部分的长度就是min(a2, b2) - max(a1, b1)。将这个原理应用到两个维度上相交部分在X轴上的宽度width max(0, min(x2, x4) - max(x1, x3))相交部分在Y轴上的高度height max(0, min(y2, y4) - max(y1, y3))相交面积area width * height公式中的max(0, ...)非常巧妙。当min(x2, x4) max(x1, x3)时说明在X轴上没有重叠此时min(x2, x4) - max(x1, x3)结果为负数或零。max(0, ...)会将其修正为0意味着宽度为0。高度计算同理。最终面积width * height如果任一维度为0结果就是0完美处理了不相交的情况。注意这里有一个初学者极易混淆的点。矩形的坐标是(左下x, 左下y, 右上x, 右上y)。在计算宽度时我们用的是x2 - x1这本身就是正数。但在计算重叠宽度时我们比较的是两个矩形右边界的最小值 (min(x2, x4)) 和两个矩形左边界的最大值 (max(x1, x3))。重叠部分左边界是两者左边界的靠右者右边界是两者右边界的靠左者。想通这一点整个公式就豁然开朗了。3. 算法思路详解与对比基于上述数学模型我们可以衍生出几种实现思路它们核心一致但在代码组织和判断逻辑上略有不同。3.1 思路一直接公式法推荐这是最简洁、最高效也是最符合数学直觉的方法。直接套用上一节推导出的公式。算法步骤读取两个矩形的8个坐标值。计算重叠部分的左下角坐标(inter_x1, inter_y1)和右上角坐标(inter_x2, inter_y2)。inter_x1 max(x1, x3)inter_y1 max(y1, y3)inter_x2 min(x2, x4)inter_y2 min(y2, y4)判断重叠矩形是否有效。如果inter_x1 inter_x2且inter_y1 inter_y2则矩形有效面积 (inter_x2 - inter_x1) * (inter_y2 - inter_y1)。否则面积 0。这个思路和之前的公式本质相同只是先显式地求出了“相交矩形”的坐标再判断其有效性。可读性更强。3.2 思路二分情况讨论法这是一种更“朴素”的思维通过几何位置关系来枚举。考虑两个矩形在X轴和Y轴上的相对位置可以分出很多种情况完全分离、包含、相交于边、相交于角等。虽然逻辑上可行但代码会非常冗长容易遗漏边界情况比如刚好相切算不算相交题目通常要求重叠面积大于0才算相交相切面积为0因此不推荐在编程题中使用。但它有助于在纸上画图理解所有可能性。3.3 思路三利用“排斥”原理计算两个矩形围成的“外包络矩形”面积然后减去两个矩形单独的面积再加上可能的重叠面积不对这是计算并集面积的容斥原理。对于交集直接使用公式法或思路一才是最直接的。对比与选择 对于机试或笔试强烈推荐使用“直接公式法”或“思路一”。它们代码量少逻辑清晰运行效率高O(1)时间复杂度且不易出错。接下来的代码实现部分将主要围绕这种思路展开。4. 多语言代码实现与深度解析我们将用五种常见的编程语言C, Java, Python, C, JavaScript来实现“直接公式法”并针对每种语言的特点和机试中的注意事项进行剖析。4.1 C 实现#include iostream #include algorithm // 用于 max 和 min 函数 using namespace std; int main() { int x1, y1, x2, y2, x3, y3, x4, y4; // 假设输入格式为空格分隔的8个整数 cin x1 y1 x2 y2 x3 y3 x4 y4; // 计算相交矩形的潜在边界 int inter_left max(x1, x3); int inter_bottom max(y1, y3); int inter_right min(x2, x4); int inter_top min(y2, y4); // 计算宽度和高度如果无重叠则结果为负数或零用max处理为0 int width max(0, inter_right - inter_left); int height max(0, inter_top - inter_bottom); // 面积 宽 * 高 int area width * height; cout area endl; return 0; }C 实现要点解析头文件algorithm提供了max和min函数比手写条件判断更简洁。输入使用cin进行标准输入这是机试中最常见的方式。务必确保变量读取顺序与题目输入格式一致。核心计算inter_left max(x1, x3)获取重叠部分左边界两个左边界中更大的那个。inter_right min(x2, x4)获取重叠部分右边界两个右边界中更小的那个。宽度即为两者之差。边界处理max(0, inter_right - inter_left)是关键。当两个矩形在X轴上分离时inter_right - inter_left为负max(0, ...)将其修正为0表示没有重叠宽度。高度同理。输出直接输出area。踩坑提醒在有的在线判题系统OJ中可能要求处理多组测试数据。上述代码只处理了一组。如果题目说明包含多组数据通常需要用while(cin x1 y1 ...)这样的循环来读取直到文件结束EOF。4.2 Java 实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取8个整数 int x1 scanner.nextInt(); int y1 scanner.nextInt(); int x2 scanner.nextInt(); int y2 scanner.nextInt(); int x3 scanner.nextInt(); int y3 scanner.nextInt(); int x4 scanner.nextInt(); int y4 scanner.nextInt(); scanner.close(); // 良好习惯关闭Scanner // 计算相交矩形边界 int interLeft Math.max(x1, x3); int interBottom Math.max(y1, y3); int interRight Math.min(x2, x4); int interTop Math.min(y2, y4); // 计算宽高利用Math.max确保非负 int width Math.max(0, interRight - interLeft); int height Math.max(0, interTop - interBottom); // 计算面积 int area width * height; System.out.println(area); } }Java 实现要点解析Scanner类这是最常用的控制台输入工具。注意nextInt()方法会读取下一个整数。Math工具类Math.max()和Math.min()是静态方法直接使用。资源管理使用完Scanner后调用close()是一个好习惯虽然在简单的单次程序中可以省略但在复杂或需要及时释放资源的场景下很重要。代码风格Java 变量命名通常采用驼峰式。算法逻辑与C版本完全一致。常见问题在华为OD的机试环境中Java类名必须为Main。务必注意大小写。此外有些OJ对Java的内存和时间限制比较严格但这种O(1)的算法完全不用担心。4.3 Python 实现def main(): # 读取一行输入分割成字符串列表再转换为整数列表 data list(map(int, input().split())) if len(data) ! 8: # 可选处理输入格式错误但题目通常保证正确 return x1, y1, x2, y2, x3, y3, x4, y4 data # 计算相交矩形边界 inter_left max(x1, x3) inter_bottom max(y1, y3) inter_right min(x2, x4) inter_top min(y2, y4) # 计算宽度和高度如果为负则取0 width max(0, inter_right - inter_left) height max(0, inter_top - inter_bottom) # 计算面积 area width * height print(area) if __name__ __main__: main()Python 实现要点解析灵活的输入处理input().split()读取一行并按空格分割。map(int, ...)将每个字符串映射为整数。list(...)转换为列表。最后使用序列解包赋值给8个变量。这是一行处理多个输入的常用技巧。内置函数Python的max()和min()是内置函数可以直接使用非常方便。简洁性Python代码通常非常简洁逻辑一目了然。width max(0, inter_right - inter_left)这行代码完美体现了Python的优雅。入口检查if __name__ __main__:是Python脚本的标准入口写法确保模块被直接运行时才执行main()函数。效率提示对于这种简单计算Python的实现速度完全足够。但在处理海量数据或复杂循环时需要注意Python的运行效率可能低于C/Java。本题不涉及。4.4 C 语言实现#include stdio.h // 自定义max和min函数因为C标准库没有直接提供 int max(int a, int b) { return (a b) ? a : b; } int min(int a, int b) { return (a b) ? a : b; } int main() { int x1, y1, x2, y2, x3, y3, x4, y4; // 读取输入 scanf(%d %d %d %d %d %d %d %d, x1, y1, x2, y2, x3, y3, x4, y4); // 计算相交矩形边界 int inter_left max(x1, x3); int inter_bottom max(y1, y3); int inter_right min(x2, x4); int inter_top min(y2, y4); // 计算宽度和高度 int width inter_right - inter_left; int height inter_top - inter_bottom; // 判断并计算面积 int area 0; if (width 0 height 0) { area width * height; } // 如果width或height 0area保持为0 printf(%d\n, area); return 0; }C 语言实现要点解析自定义工具函数C语言标准库没有max/min函数需要自己实现。这里使用了三元运算符? :简洁高效。输入输出使用scanf和printf注意scanf需要传递变量的地址运算符。逻辑判断C语言版本没有使用max(0, width)的技巧而是先计算出width和height然后通过if (width 0 height 0)来判断是否真正相交。这种写法更符合C语言的直白风格逻辑同样清晰。效率C语言的实现通常效率最高但代码量稍多。对于算法题清晰性比极致的微优化更重要。边界情况这里判断条件是width 0 height 0。如果题目定义两个矩形边重合即width 0或height 0不算相交那么这个判断是正确的。如果题目定义重合也算相交面积为0那么条件应该改为width 0 height 0。通常机试题默认是“有重叠区域”才算相交即面积大于0所以的判断是安全的。务必仔细审题。4.5 JavaScript (Node.js) 实现假设在华为OD的机试环境或其他支持Node.js的OJ中我们需要处理控制台输入。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); rl.on(line, (input) { // 将输入行按空格分割并转换为数字 const numbers input.trim().split(/\s/).map(Number); if (numbers.length ! 8) { return; // 输入格式错误处理 } const [x1, y1, x2, y2, x3, y3, x4, y4] numbers; // 计算相交矩形边界 const interLeft Math.max(x1, x3); const interBottom Math.max(y1, y3); const interRight Math.min(x2, x4); const interTop Math.min(y2, y4); // 计算宽度和高度 const width Math.max(0, interRight - interLeft); const height Math.max(0, interTop - interBottom); // 计算面积 const area width * height; console.log(area); // 如果只有一行输入可以关闭rl。如果是多行且这是最后一行也需要处理。 // rl.close(); }); // 注意对于单次输入上述代码足够。如果题目是多组数据需要累积处理或每行独立计算。JavaScript 实现要点解析输入模块Node.js中使用readline模块来逐行读取标准输入。这是处理算法题输入的标准方式。数据处理input.trim().split(/\s/).map(Number)是一个经典组合去除首尾空格按一个或多个空白字符分割然后将每个部分转换为数字。解构赋值const [x1, y1, ...] numbers是ES6的语法能优雅地将数组元素赋值给变量。Math对象和Java一样使用Math.max()和Math.min()。异步事件rl.on(line, ...)是事件监听器每读到一行数据就会触发回调函数。对于单次输入在回调函数里计算并输出即可。对于多次输入可能需要将rl.close()放在合适的时机或者累积数据。环境差异不同的OJ对JavaScript的支持可能不同。有的可能要求使用console.log输出有的可能要求将结果作为函数返回值。华为OD的机试环境通常会有明确的题目输入输出说明请务必按照平台要求调整代码框架。例如有时可能需要写一个function solve(input)之类的函数。5. 边界条件与测试用例设计一道题能否ACAccepted往往取决于是否考虑了所有边界条件。对于“矩形相交的面积”以下测试用例至关重要测试用例描述输入样例 (x1 y1 x2 y2 x3 y3 x4 y4)预期输出验证点常规相交0 0 2 2 1 1 3 31标准相交面积1包含关系0 0 5 5 1 1 3 34一个矩形完全在另一个内部不相交分离0 0 1 1 2 2 3 30完全分离相切于边0 0 2 2 2 0 4 20X轴上右边界与左边界重合无重叠面积相切于点0 0 2 2 2 2 4 40右上角与左下角重合无重叠面积负坐标相交-2 -2 0 0 -1 -1 1 11坐标包含负数逻辑不变大整数0 0 1000000 1000000 500000 500000 1500000 1500000250000000000验证是否使用int足够面积可能超出32位int范围退化矩形0 0 0 5 1 1 3 30第一个矩形宽度为0不是有效矩形但题目通常保证输入有效此用例可测鲁棒性关于数据类型的选择 从最后一个“大整数”用例可以看出当坐标值很大时宽度和高度的差值可能很大相乘后的面积可能超出普通int32位有符号最大值约21亿的范围。在C、Java中可以使用long long(C) 或long(Java) 来存储面积。在Python中整数是任意精度的无需担心。在C语言中可以使用long long。在JS中使用Number双精度浮点但整数在安全范围内2^53以下是精确的对于机试通常足够。修正后的C版本考虑大数#include iostream #include algorithm using namespace std; int main() { long long x1, y1, x2, y2, x3, y3, x4, y4; // 使用long long cin x1 y1 x2 y2 x3 y3 x4 y4; long long inter_left max(x1, x3); long long inter_bottom max(y1, y3); long long inter_right min(x2, x4); long long inter_top min(y2, y4); long long width max(0LL, inter_right - inter_left); // 注意0LL long long height max(0LL, inter_top - inter_bottom); long long area width * height; cout area endl; return 0; }6. 常见错误与调试技巧在实现这道题时新手常会遇到以下几个问题坐标顺序混淆误将(x1, y1)和(x2, y2)当成左上角和右下角。务必确认题目描述本题是左下角和右上角。如果题目给的是左上和右下公式需要调整重叠部分上边界是min(y1, y3)下边界是max(y2, y4)因为Y轴向下为正。边界条件判断错误错误写法if (x3 x2 x4 x1 ...)这种判断条件非常容易遗漏或写错边界。正确做法坚持使用max和min推导重叠边界然后用if (width 0 height 0)或max(0, ...)来判断。这是最不容易出错的方法。数据类型溢出如第5节所述当坐标值很大时中间结果和最终面积可能溢出32位整数。在不确定的情况下统一使用64位整数long long/long是更安全的选择。输入格式处理不当机试系统输入可能是空格分隔也可能是换行分隔。我们的代码通常按空格分隔读取 (cin ,scanf(“%d”),input().split())。如果题目明确是换行分隔可能需要多次读取。仔细阅读题目输入说明。多组测试数据未处理有些题目会说明“输入包含多组测试数据”代码需要用循环包裹核心逻辑直到读取到文件结束符EOF。例如// C 多组数据示例 int x1, y1, x2, y2, x3, y3, x4, y4; while (cin x1 y1 x2 y2 x3 y3 x4 y4) { // ... 计算并输出面积 ... }调试技巧画图当不确定时在纸上画出两个矩形的相对位置标出坐标手动计算重叠区域。这是最直观的调试方法。打印中间变量在代码中打印出计算出的inter_left,inter_right,width等中间结果看是否符合预期。使用第5节的测试用例逐一测试特别是边界用例确保都能通过。7. 举一反三与相关题型拓展掌握了矩形相交你可以轻松解决一系列相关的几何和算法问题矩形合并Union面积计算两个矩形覆盖的总面积。可以用容斥原理面积A 面积B - 相交面积。核心仍然是计算相交面积。多个矩形相交给定多个矩形判断其中任意两个是否相交或者求所有矩形的公共相交区域可能不存在。对于公共区域可以转化为求所有矩形在X轴投影的交集和Y轴投影的交集。即公共左边界 max(所有矩形左边界)公共右边界 min(所有矩形右边界)公共下边界 max(所有矩形下边界)公共上边界 min(所有矩形上边界)然后判断width和height是否大于0。轴对齐矩形AABB的碰撞检测在游戏开发或图形学中判断两个轴对齐的包围盒AABB是否碰撞其原理和本题一模一样。这是最基础的碰撞检测算法。LeetCode 相关题目223. 矩形面积计算两个矩形覆盖的总面积直接应用容斥原理。836. 矩形重叠判断两个矩形是否重叠是本题的简化版只需判断是否相交无需计算面积。850. 矩形面积 II计算多个矩形覆盖的总面积难度较大需要用到扫描线算法。从2D推广到3D在三维空间中判断两个轴对齐的立方体AABB是否相交原理完全一致只是多了一个Z维度。相交当且仅当在X、Y、Z三个轴上的投影区间都相交。这道“矩形相交的面积”题就像一把钥匙帮你打开了计算几何中“轴对齐边界框”问题的大门。它的核心思想——将高维问题分解为多个一维独立子问题——是一种非常重要的算法思维。在华为OD乃至其他技术面试中展现出对这种基础问题深刻、清晰且严谨的理解远比死记硬背复杂的算法更能体现你的基本功和思维能力。