> 文档中心 > acwing 每日一题 1761.阻挡广告牌

acwing 每日一题 1761.阻挡广告牌

题目描述:(不想读题直接看最后的分析

在漫长的产奶期间,奶牛贝茜喜欢透过窗户盯着马路对面的两个巨大的矩形广告牌,上面写着“农夫亚历克斯的惊人开胃苜蓿”和“农夫格雷格的大粒谷物”。
广告牌上这两种精美的牛饲料看上去比农场里的草美味的多。
有一天,当贝茜凝视着窗外时,她惊异地看到一辆巨大的矩形卡车停在马路对面。
卡车的侧面有一个广告,上面写着“农夫史密斯的精湛牛排”。
贝茜对此不太感兴趣,但她非常担心卡车可能会阻挡她观看最喜欢的两个广告牌的视野。
给定两个广告牌的位置和卡车的位置,请计算两个广告牌的仍然可见的总面积。
卡车可能挡到两个广告牌或只挡到其中一个,或都挡不到。

输入格式:

第一行包含四个整数 x1,y1,x2,y2,其中 (x1,y1) 和 (x2,y2) 表示在贝茜的二维视野中,第一个广告牌的左下角和右上角坐标
第二行按照如上形式,包含四个整数,表示第二个广告牌的左下角和右上角坐标。
第三行按照如上形式,包含四个整数,表示卡车侧面的左下角和右上角坐标。

输出格式:

输出两个广告牌的仍然可见的总面积。

数据范围:

−1000≤x1,y1,x2,y2≤1000,保证两个广告牌之间重叠面积不大于 0。

输入样例:

1 2 3 5
6 0 10 4
2 1 8 3

输出样例:

17

样例解释:

第一块广告牌的可见面积为 5,第二块广告牌的可见面积为 12。

分析:(这种求重叠面积的题之前遇到几次,这次把结论记下,下次不用自己画图推了┭┮﹏┭┮)

题目的意思,有两块不会重叠的广告牌,和一个车,都是矩形的,给出每个矩形的最下角和右上角坐标,车可能会和0/1/2块广告牌重叠,请求出没有重叠的广告牌的总面积。

拿到题目就觉得简单,估计有公式的,于是尝试画图分析了一波,几经折腾,终于找到公式。

我们可以分析每一块广告牌与车是否重叠,然后把没有重叠的面积加起来。

先假设广告牌的坐标为左下角(x1, y1)和右上角(x2, y2),车车左下角(a1, b1)和右上角(a2, b2)。

可以分为三种情况:

情况一:没有重叠,简单,就是判断坐标的边界,x2 = a2 || y2 = b2。

情况二:车车遮挡完了广告牌(也是🐂🐂🐂了,红色的车车)

 广告牌的坐标被车车坐标包围起来,x1 >= a1 && y1 >= b1 && x2 <= a2 && y2 <= b2。

情况三:看似比较复杂(只要细心观察,很简单)

这时候,两个矩形遮挡面积 = (两矩形的右上角最小x坐标:x2 - 两矩形的左下角最大x坐标:a1) * (两矩形的右上角最小y坐标 - 两矩形的左下角最大y坐标)。比如上图中 = (x2 - a1) * (b2 - y1)。

那么代码就简单了:

#include#includeusing namespace std;int f(int x1, int y1, int x2, int y2, int a1, int b1, int a2, int b2){  // 前四个是广告牌坐标    // 1、没有遮挡    if(x2 = a2 || y2 = b2) return (y2 - y1) * (x2 - x1);     // 2、广告牌被完全遮挡    else if(x1 >= a1 && y1 >= b1 && x2 <= a2 && y2 >x1>>y1>>x2>>y2;  // 第一块广告牌坐标    cin>>a1>>b1>>a2>>b2;  // 第二块广告牌坐标    cin>>kx1>>ky1>>kx2>>ky2; // 车车坐标    cout << f(x1, y1, x2, y2, kx1, ky1, kx2, ky2) + f(a1, b1, a2, b2, kx1, ky1, kx2, ky2);    return 0;}