题目描述题目要求判断两个轴对齐的矩形是否重叠若重叠则输出重叠区域的左下角和右上角坐标。矩形由左下角坐标(XLL,YLL)(X_{LL}, Y_{LL})(XLL​,YLL​)和右上角坐标(XUR,YUR)(X_{UR}, Y_{UR})(XUR​,YUR​)定义且满足XLLXURX_{LL} X_{UR}XLL​XUR​、YLLYURY_{LL} Y_{UR}YLL​YUR​。若两矩形仅边重合而无内部重叠视为不重叠。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例包含两行每行四个整数分别表示第一个矩形和第二个矩形的左下角和右上角坐标。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例若两矩形不重叠输出No Overlap否则输出四个整数重叠矩形的左下角xxx、左下角yyy、右上角xxx、右上角yyy。两个连续测试用例的输出之间由一个空行分隔。样例输入1 0 20 100 120 80 50 500 60输出80 50 100 60题目分析本题的核心是计算两个轴对齐矩形的交集。重叠判断设矩形R1R_1R1​的左下角(x1,y1)(x_1, y_1)(x1​,y1​)、右上角(x2,y2)(x_2, y_2)(x2​,y2​)矩形R2R_2R2​的左下角(x3,y3)(x_3, y_3)(x3​,y3​)、右上角(x4,y4)(x_4, y_4)(x4​,y4​)。则重叠矩形的左下角坐标为lowxmax⁡(x1,x3),lowymax⁡(y1,y3) \textit{lowx} \max(x_1, x_3),\quad \textit{lowy} \max(y_1, y_3)lowxmax(x1​,x3​),lowymax(y1​,y3​)右上角坐标为upxmin⁡(x2,x4),upymin⁡(y2,y4) \textit{upx} \min(x_2, x_4),\quad \textit{upy} \min(y_2, y_4)upxmin(x2​,x4​),upymin(y2​,y4​)若lowx≥upx\textit{lowx} \ge \textit{upx}lowx≥upx或lowy≥upy\textit{lowy} \ge \textit{upy}lowy≥upy则两矩形无重叠包括仅边重合的情况。否则重叠矩形即为(lowx,lowy,upx,upy)(\textit{lowx}, \textit{lowy}, \textit{upx}, \textit{upy})(lowx,lowy,upx,upy)。注意点坐标均为整数范围000到999999999999。仅边重合如一个矩形的右边与另一个矩形的左边重合时lowxupx\textit{lowx} \textit{upx}lowxupx属于不重叠。复杂度分析每个测试用例只需常数时间计算。代码实现// Overlapping Rectangles// UVa ID: 460// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases;cincases;intx1,y1,x2,y2,x3,y3,x4,y4;for(inti1;icases;i){if(i1)cout\n;cinx1y1x2y2;cinx3y3x4y4;intlowxmax(x1,x3),lowymax(y1,y3),upxmin(x2,x4),upymin(y2,y4);if(lowxupx||lowyupy)coutNo Overlap\n;elsecoutlowx lowy upx upy\n;}return0;}