python/TangDou/AcWing/759.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 10010;

//结构体
struct Segment {
    int k;      //行号或列号
    int l, r;   //左右坐标
    //自定义一个排序的规则
    bool operator<(const Segment &w) const {//重载<先按行/列，再按左右端点   行/列---左端点---右端点
        if (k != w.k) return k < w.k;
        if (l != w.l) return l < w.l;
        return r < w.r;
    }
};

//区间合并的核心函数
LL merge(vector<Segment> &q) { //注意这里与老师的vector<PII>不同，因为是二维的，需要传入一个结构体的数组
    vector<Segment> w;          //合并的临时对象
    sort(q.begin(), q.end());   //按自定义排序方法进行排序

    LL res = 0;
    for (int i = 0; i < q.size();) {//+
        int j = i;
        while (j < q.size() && q[j].k == q[i].k) j++;//相同行/列坐标范围

        int l = -2e9, r = l - 1;
        for (int k = i; k < j; k++) {//+，++是On
            if (r < q[k].l) {           //没有交集，需要把这组数据入结果集
                //更新一下长度
                res += r - l + 1;
                //下面是老师的标准套路
                if (l != -2e9) w.push_back({q[i].k, l, r});
                l = q[k].l, r = q[k].r;
            } else r = max(q[k].r, r); //有交集，把1和2放在一起写，参考803.cpp
        }
        if (l != -2e9) w.push_back({q[i].k, l, r});//最后一组塞进去
        //更新一下长度
        res += r - l + 1;
        //开始下一行或下一列的数据
        i = j;
    }
    q = w;//拷贝回来 直接等于号就行
    return res;
}

int main() {
    //输入+输出重定向
    freopen("../AcWing/N3/759.txt", "r", stdin);
    int n;
    cin >> n;

    //声明两个结构体数组
    vector<Segment> rows, cols;

    //读入数据
    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) cols.push_back({x1, min(y1, y2), max(y1, y2)});//如果是行相同，那么是列数据，读入到列数组中。并且学习一下这个min和max的用法，挺好用！
        else rows.push_back({y1, min(x1, x2), max(x1, x2)});//同上，相反的
    }
    //将行和列数组分别进行合并，并且返回区间内的方格个数，加在一起，这样肯定会有叠加两次的，还需要进一步去重
    LL res = merge(rows) + merge(cols);

    //双重循环，对于叠加的进行去重
    for (auto r:rows)
        for (auto c:cols)
            if (r.k >= c.l && r.k <= c.r && c.k >= r.l && c.k <= r.r)
                res--;

    cout << res << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}