算法学习：每日一练 No.223

今天的题目比较简单，可是我的脑子实在太笨了。

223. 矩形面积

要求解的是这两个矩形覆盖的总面积。

用容斥原理可以解决这道题，最终的总面积 = 矩形a的面积 + 矩形b的面积 - a与b相交的面积。

只要求得相交的面积这题就可以宣告结束了，那么该如何用代码去求解呢？

我这个比较笨的思路

令重合部分的矩形为C，要求得C的面积首先要知道边长，边长也是ab两个矩形重合部分的边长。C在X轴上的投影取决于[ax1,ax2]和[bx1,bx2]，目的就是求解这两个区间的交集。

区间的交集取决于ab两个矩形的关系，从图上倒是可以清晰的得知ab两个矩形的关系，即ax1 < bx1 < ax2 < bx2，如果扩展到任意两个矩形又应该如何判断呢？

现在我们只关注X轴上的投影区间，我们将ab扩展为平面上任意两个矩形，得到的投影区间的关系如下：

区间关系	是否重合
ax1 < ax2 <= bx1 < bx2	不重合
ax1 <= bx1 < ax2 <= bx2	重合
ax1 <= bx1 < bx2 <= ax2	重合
bx1 <= ax1 < bx2 <= ax2	重合
bx1 < bx2 <= ax1 < ax2	不重合

总而言之，如果是重合的情况，我们只需要将数组[ax1,ax2,bx1,bx2]排序后的中间两项做差，就能得到我们要的边长了。

想起来是这样，不过判断的过程就有些复杂了吧？尝试写一下判断的逻辑。

bool isCoincide(int ax1,int ax2,int bx1,int bx2)
{
    if(ax2 <= bx1 || bx2 <= ax1)
    {
        return false;
    }
    return true;
}

经过上表的总结，判断不重合比判断重合要方便许多，因为在这道题当中x1一定小于x2，所以不重合的情况只需要判断x2和x1的情况就好了。

X轴的投影区间是否重合可以用上述代码来进行判断，同理，Y轴的情况也可以使用上述代码。

写出来的程序大概是这个样子：

#include <algorithm>
#include <vector>
using namespace std;
class Solution
{
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
    {
        vector<int> coincideX = {ax1, ax2, bx1, bx2};
        vector<int> coincideY = {ay1, ay2, by1, by2};
        int coincideArea = 0;
        if (isCoincide(ax1, ax2, bx1, bx2) && isCoincide(ay1, ay2, by1, by2))
        {
            sort(coincideX.begin(), coincideX.end());
            sort(coincideY.begin(), coincideY.end());
            coincideArea = (coincideX[2] - coincideX[1]) * (coincideY[2] - coincideY[1]);
        }
        return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - coincideArea;
    }
    bool isCoincide(int ax1, int ax2, int bx1, int bx2)
    {
        if (ax2 <= bx1 || bx2 <= ax1)
        {
            return false;
        }
        return true;
    }
};
int main(int argc, char const *argv[])
{
    int ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2;
    Solution s;
    int res = s.computeArea(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
    return 0;
}

这样耗费的时间和空间都很多，很不聪明，很不值当，我很讨厌自己，虽然能解出正确的答案。

聪明的解法

看了题解我才明白，可以这么简单。

投影区间的交集嘛，无非就是左端点取值最大的，右端点取值最小的，两者相减即是边长。

没有交集的时候这个值会是负数，最终求解面积的时候将该值与0取一个max()即可。

直接上代码：

#include <algorithm>
using namespace std;
class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int area1 = (ax2 - ax1) * (ay2 - ay1);
        int area2 = (bx2 - bx1) * (by2 - by1);
        int width3 = std::max(std::min(ax2, bx2) - std::max(ax1, bx1), 0);
        int length3 = std::max(std::min(ay2, by2) - std::max(ay1, by1), 0);
        return area1 + area2 - width3 * length3;
    }
}; 