79 lines
2.7 KiB
C++
79 lines
2.7 KiB
C++
#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;
|
||
} |