阻挡广告牌II

阻挡广告牌II

题目

奶牛贝茜曾经从农场中向外看去，可以看到两个刊登着美味的牛饲料广告的广告牌，这令她非常满意。

不幸的是，其中一个广告牌最近已更新，现在刊登着广告“农民拉里的割草机”。

但是贝茜可不喜欢割草机，这些割草机只会把她爱吃的草割的一干二净。

幸运的是，剩下的牛饲料广告牌位于割草机广告牌的前面，有可能将其遮挡住。

贝茜希望这个讨厌的割草机广告牌能够完全从自己的视线中消失，并为此制定了一个冒险计划。

她计划从谷仓里偷一个大的矩形防水布，并在深夜偷偷溜走，用它覆盖割草机广告牌的其余部分，使得她能完全看不到割草机广告牌。

给定两个广告牌的位置，请帮助贝茜计算她所需要的防水布的最小面积。

由于谷仓中只有矩形的防水布，因此贝茜发现为了将割草机广告牌完全遮盖，所需的防水布面积可能会大于割草机广告牌的裸露面积，如下例所示。

防水布在放置时，其边必须与广告牌的边平行，即不能倾斜放置。

输入格式

第一行包含四个整数 x₁,y₁,x₂,y₂，其中 (x₁,y₁) 和 (x₂,y₂) 表示割草机广告牌的左下角和右上角坐标。

第二行按照如上形式，包含四个整数，表示牛饲料广告牌的左下角和右上角坐标。

牛饲料广告牌可能完全遮盖了割草机广告牌，或部分遮盖了割草机广告牌，也可能完全没有遮盖割草机广告牌。

输出格式

输出用来遮盖割草机广告牌的防水布的最小面积。

数据范围

−1000≤x₁,y₁,x₂,y₂≤1000

输入样例：

2 1 7 4
5 -1 10 3

输出样例：

15

样例解释

虽然牛饲料广告牌遮盖住了割草机广告牌的右下角的一部分，但这并没有起到作用。

想要完全遮盖割草机广告牌，仍然需要一块和它尺寸相同的防水布。

思路

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N=2010,B=N/2;bool st[N][N];int main()
{int a,b,c,d;cin>>a>>b>>c>>d;a+=B,b+=B,c+=B,d+=B;for(int i=a;i<c;i++){for(int j=b;j<d;j++){st[i][j]=true;}}cin>>a>>b>>c>>d;a+=B,b+=B,c+=B,d+=B;for(int i=a;i<c;i++){for(int j=b;j<d;j++){st[i][j]=false;}}a=b=N,c=d=0;for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(st[i][j]){a=min(a,i),c=max(c,i);b=min(b,j),d=max(d,j);}}}int w=max(0,c-a+1),h=max(0,d-b+1);cout<<w*h<<endl;return 0;
}