1749. 阻挡广告牌 II

1749. 阻挡广告牌 II

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

−1000≤x1,y1,x2,y2≤1000

输入样例：

2 1 7 4
5 -1 10 3

输出样例：

15

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

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

代码:

// 覆盖一个可能不规则的矩形
#include <bits/stdc++.h>
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] = 1;}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] = 0;}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;
}