[算法|基础算法] 51nod-2-4
题目描述
在二维平面上，给定两个矩形，满足矩形的每条边分别和坐标轴平行，求这个两个矩形的并的面积。即它们重叠在一起的总的面积。
输入格式
8个数，分别表示第一个矩形左下角坐标为(A,B)，右上角坐标为(C,D)；第二个矩形左下角坐标为(E,F)，右上角坐标为(G,H)。
保证A<C，B<D，E<G，F<H。
保证所有数的绝对值不超过2*10^9，矩形并的面积≤2*10^9。
输出格式
输出一个数表示矩阵并的面积。
样例输入#1
-3 0 3 4 0 -1 9 2
样例输出#1
45
思想
大水题做了我半天，就是个弟弟。
首先有题目读错。当作了完全覆盖部分，之后一直在处理边的关系，最后发现只要两矩形相交，就可以将行边和列边分别sort，其中的第3条减第2条的长度即必然为相交长度，两结果相乘即可。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define M 1005
#define bg(x) cout<<"Debug: "<<x<<endl
#define bg2(x,y) cout<<"Dbg2: "<<x<<", "<<y<<endl
using namespace std;
const int inf=0x7f7f7f7f;
long long a[4],b[4];
int main()
{
ios::sync_with_stdio(false);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>a[0]>>b[0]>>a[1]>>b[1]>>a[2]>>b[2]>>a[3]>>b[3];
long long s1=(a[1]-a[0])*(b[1]-b[0]);
long long s2=(a[3]-a[2])*(b[3]-b[2]);
if((a[1]<=a[2]||a[3]<=a[0])||(b[1]<=b[2]||b[3]<=b[0]))
{
cout<<s1+s2<<endl;
return 0;
}
sort(a,a+4);
sort(b,b+4);
cout<<(a[2]-a[1])*(b[2]-b[1])<<endl;
cout<<s1+s2-(a[2]-a[1])*(b[2]-b[1])<<endl;
return 0;
}