计算几何

两直线覆盖的长度 = l1 + l2 - (l1 ∩ l2)。该题重点的如何求相交部分。

一维：线段的交集

一维两线段相交长度为：max(0, min(b, d) - max(a, c))

二维：矩形的交集

将相交的部分分别对x轴和y轴进行投影，相当于降维到一维形式再做。

投影到x轴的长度：max(0, min(ax2, bx2) - max(ax1, bx1))

投影到x轴的长度：max(0, min(ay2, by2) - max(ay1, by1))

时间复杂度$O(1)$，空间复杂度$O(1)$

AC代码

class Solution {
public:
    typedef long long LL;
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        LL x = max(0ll, min(ax2, bx2) - max(ax1, bx1) + 0ll);
        LL y = max(0ll, min(ay2, by2) - max(ay1, by1) + 0ll);
        LL s1 = (ax2 - ax1) * (ay2 - ay1);
        LL s2 = (bx2 - bx1) * (by2 - by1);  
        return s1 + s2 - x * y;
    }
};