|
|
#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;
|
|
|
} |
