#include<iostream>
#include<algorithm>
using namespace std;
#define fio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
const int N = 1e4 + 3;
struct seg {
int k, l, r;
};
vector<seg>row(N), col(N);
int t1 = 0, t2 = 0;
int n;
bool cmp(const struct seg& a, const struct seg& b) {
if(a.k != b.k) return a.k < b.k;
if(a.l != b.l) return a.l < b.l;
if(a.r != b.r) return a.r < b.r;
return 0;
}
ll mg(vector<seg> & q, int t) {
vector<seg>w;
ll res = 0;
int i = 0,j = 0;
while(i < t) {
while(j < t && q[i].k == q[j].k) ++j;
int l = q[i].l, r = q[i].r;
for(int k = i + 1; k < j; ++k) {
if(q[k].l <= r) r = max(q[k].r, r);
else {
res += r - l + 1;
w.push_back({q[i].k, l, r});
l = q[k].l, r = q[k].r;
}
}
res += r - l + 1;
w.push_back({q[i].k, l, r});
i = j;
}
q = w;
return res;
}
int main() {
fio;
cin>>n;
int x1, y1, x2, y2;
for(int i = 0; i < n; ++i) {
cin>>x1 >> y1>> x2 >> y2;
if(x1 == x2) row[t1++] = {x1, min(y1, y2), max(y1, y2)};
else col[t2++] = {y1, min(x1, x2), max(x1, x2)};
}
sort(row.begin(), row.begin() + t1, cmp);
sort(col.begin(), col.begin() + t2, cmp);
ll ans = mg(row, t1) + mg(col, t2);
t1 = row.size(), t2 = col.size();
for(int i = 0; i < t1; ++i) {
for(int j = 0; j < t2; ++j) {
if(row[i].k >= col[j].l && row[i].k <= col[j].r && col[j].k >= row[i].l && col[j].k <= row[i].r)
--ans;
}
}
cout<<ans;
return 0;
}
/*
10
-1 0 -1 2
-10 6 -10 3
0 4 0 -3
-4 2 -4 6
-10 -6 -10 6
9 5 9 7
9 -1 0 -1
5 2 5 -7
8 -1 -2 -1
4 7 4 -7*/
区间合并题,去重题,O(nlogn + (n^2)/4),这里根据均值定理,(n^2)/4不超过250000000,可以
这个关键时间在排序和横纵段相交时的去重,细节很多,
首先可以根据输入的段类型分成横段和纵段
输入分类时注意,这里输入坐标不一定是先小后大,要自己判断
在横段内根据先小编号在小左端点最后右端点排序,
这时数组内的元素就是根据编号排在一起
找到每个边界的分界位置,同时合并这一行/列的所有段,注意这里是真合并,最后要更新原始向量,防止最后统计
横纵相交时重复统计,每次合并时 维护返回值,即区间长度累加和
最后固定每一行,遍历每一列段,统计,这里相交只可能为1,所以–,最后就是答案