#include 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 &q) { //注意这里与老师的vector不同,因为是二维的,需要传入一个结构体的数组 vector 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 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; }