题目描述
题目要求判断两个轴对齐的矩形是否重叠，若重叠则输出重叠区域的左下角和右上角坐标。矩形由左下角坐标(XLL,YLL)(X_{LL}, Y_{LL})(XLL,YLL)和右上角坐标(XUR,YUR)(X_{UR}, Y_{UR})(XUR,YUR)定义，且满足XLL<XURX_{LL} < X_{UR}XLL<XUR、YLL<YURY_{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)。则重叠矩形的左下角坐标为：
lowx=max(x1,x3),lowy=max(y1,y3) \textit{lowx} = \max(x_1, x_3),\quad \textit{lowy} = \max(y_1, y_3)lowx=max(x1,x3),lowy=max(y1,y3)
右上角坐标为：
upx=min(x2,x4),upy=min(y2,y4) \textit{upx} = \min(x_2, x_4),\quad \textit{upy} = \min(y_2, y_4)upx=min(x2,x4),upy=min(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。
- 仅边重合（如一个矩形的右边与另一个矩形的左边重合）时，lowx=upx\textit{lowx} = \textit{upx}lowx=upx，属于不重叠。
复杂度分析
每个测试用例只需常数时间计算。
代码实现
// Overlapping Rectangles// UVa ID: 460// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases;cin>>cases;intx1,y1,x2,y2,x3,y3,x4,y4;for(inti=1;i<=cases;i++){if(i>1)cout<<'\n';cin>>x1>>y1>>x2>>y2;cin>>x3>>y3>>x4>>y4;intlowx=max(x1,x3),lowy=max(y1,y3),upx=min(x2,x4),upy=min(y2,y4);if(lowx>=upx||lowy>=upy)cout<<"No Overlap\n";elsecout<<lowx<<' '<<lowy<<' '<<upx<<' '<<upy<<'\n';}return0;}
