最大面积时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛牛有两个矩形这两个矩形放在一个y O x yOxyOx坐标系内且矩形的四条边均与坐标轴平行。规定与x xx轴平行的边为矩形长与y yy轴平行的边为矩形高。矩形1 11的长与高分别为a , b a, ba,b矩形2 22的长与高分别为c , d c, dc,d牛牛现在想随意摆放这两个矩形但不能改变这两个矩形的长与高他想知道这两个矩形最大的相交面积是多大输入描述一行四个整数a , b , c , d ( 1 ≤ a , b , c , d ≤ 10 6 ) a, b, c, d\ (1 \le a, b, c, d \le 10^6)a,b,c,d(1≤a,b,c,d≤106)前两个整数表示矩形1 11的长与高后两个整数表示矩形2 22的长与高。输出描述一个整数表示这两个矩形最大的相交面积。示例 1输入2 2 3 2输出4说明如图所示为样例所给的两个矩形。上图为最大面积的一种摆放方式找不到比这个面积更大的摆放方式因此最大重叠面积为2 × 2 4 2 \times 2 42×24。数据范围与提示1 ≤ a , b , c , d ≤ 10 6 1 \le a, b, c, d \le 10^61≤a,b,c,d≤106解题思路本题是矩形最大相交面积的经典题型核心是两矩形长与高不可改变、长边恒水平、高边恒垂直不可旋转相交区域的宽与高分别受两矩形对应边长约束故最优面积就是把两个维度分别取较小边长后相乘。1. 问题等价转化可自由平移两矩形可任意摆放只受边长不可变、长边水平、高边垂直约束因此可自由对齐平移只需关心两者在两坐标轴投影区间的重叠量。不可旋转题中已规定与x xx轴平行的边为长、与y yy轴平行的边为高且不得改变长与高故长边只能水平、高边只能垂直不存在旋转换向的可能。重叠宽度上界两矩形在x xx方向投影的重叠长度不可能超过任一矩形的宽故重叠宽 ≤ min ⁡ ( a , c ) 重叠宽\le\min(a,c)重叠宽≤min(a,c)。重叠高度上界同理重叠高 ≤ min ⁡ ( b , d ) 重叠高\le\min(b,d)重叠高≤min(b,d)。上界可达使x xx方向投影完全对齐重叠宽 min ⁡ ( a , c ) \min(a,c)min(a,c)、y yy方向投影完全对齐重叠高 min ⁡ ( b , d ) \min(b,d)min(b,d)两方向可独立满足故上界可同时取到。2. 算法实现两维分别取小再相乘读入读入四个整数a , b , c , d a,b,c,da,b,c,d。分别取小水平方向取min ⁡ ( a , c ) \min(a,c)min(a,c)垂直方向取min ⁡ ( b , d ) \min(b,d)min(b,d)。结果聚合两方向相互独立面积即二者之积输出min ⁡ ( a , c ) × min ⁡ ( b , d ) \min(a,c)\times\min(b,d)min(a,c)×min(b,d)。3. 复杂度分析时间复杂度O ( 1 ) O(1)O(1)仅两次比较与一次乘法。空间复杂度O ( 1 ) O(1)O(1)只占用若干整型变量。总结核心逻辑相交面积 重叠宽 × 重叠高而重叠宽不超过min ⁡ ( a , c ) \min(a,c)min(a,c)、重叠高不超过min ⁡ ( b , d ) \min(b,d)min(b,d)且该上界可通过平移对齐同时取到。关键操作对两个维度分别取较小边长再相乘。效率保障单次常数级运算即得答案10 6 10^6106量级数据毫无压力远低于 1 秒限制。代码简要说明类型与常量typedef long long ll、ull、vvt、pll以及N/M/INF/mod均为模板残留本题未使用可忽略。溢出处理a , b , c , d ≤ 10 6 a,b,c,d\le10^6a,b,c,d≤106结果最大约10 12 10^{12}1012超出 32 位int范围故用long longll承接乘积避免溢出。主函数读入a , b , c , d a,b,c,da,b,c,d后直接计算min(a,c)*min(b,d)并输出。输入输出优化ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);提升 I/O 效率本题数据量极小属通用习惯。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b,c,d;cinabcd;coutmin(a,c)*min(b,d)endl;return0;}