CSES Geometry - Star's Blog

2025-01-17：还差两道题，预计明天完结！！

主要是为了补全队的短板，我开始学之前看都不看的计算几何了，毕竟谁不想做香香软软的数据结构呢。另外如果有人看的话，前排提醒一下，这不是详细的题解，只是记录一下自己做的过程。

做这个板子题的题集之前我先看了 Acwing 的课，所以码风会和y总的比较相似。

Point Location Test#

叉积判断一下就行。

1
#include <iostream>
2
#define x first
3
#define y second
4
using namespace std;
5
typedef long long LL;
6
typedef pair<LL, LL> PLL;
7
const int N = 100010;
8

9
LL gcd(LL a, LL b) {
10
    return b ? gcd(b, a % b) : a;
11
}
12

13
PLL operator -(PLL a, PLL b) {
14
    return {a.x - b.x, a.y - b.y};
15
}
16

17
LL operator *(PLL a, PLL b) {
18
    return a.x * b.y - a.y * b.x;
19
}
20

21
LL area(PLL a, PLL b, PLL c) {
22
    return (b - a) * (c - a);
23
}
24

25
PLL a[N];
26

27
int main() {
28
    int n;
29
    scanf("%d", &n);
30
    for (int i = 0; i < n; ++i) {
31
        scanf("%lld%lld", &a[i].x, &a[i].y);
32
    }
33
    a[n] = a[0];
34
    LL s = 0, cnt[2] = {0, 0};
35
    for (int i = 0; i < n; ++i) {
36
        s += area({0, 0}, a[i], a[i + 1]);
37
        cnt[1] += abs(gcd(a[i].x - a[i + 1].x, a[i].y - a[i + 1].y));
38
    }
39
    cnt[0] = (abs(s) - cnt[1]) / 2 + 1;
40
    printf("%lld %lld\n", cnt[0], cnt[1]);
41
    return 0;
42
}

Line Segment Intersection#

也是叉积判断一下就行，但是这个需要特判共线的情况。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#define x first
5
#define y second
6

7
using namespace std;
8
typedef long long LL;
9
typedef pair<LL, LL> PLL;
10

11
PLL operator -(PLL a, PLL b) {
12
    return {a.x - b.x, a.y - b.y};
13
}
14

15
LL operator *(PLL a, PLL b) {
16
    return a.x * b.y - a.y * b.x;
17
}
18

19
LL area(PLL a, PLL b, PLL c) {
20
    return (b - a) * (c - a);
21
}
22

23
int sign(LL x) {
24
    if (x == 0) return 0;
25
    else if (x < 0) return -1;
26
    else return 1;
27
}
28

29
bool in_mid(PLL a, PLL b, PLL c) {
30
    vector<PLL> v ={a, b, c};
31
    sort(v.begin(), v.end());
32
    return v[1] == c;
33
}
34

35
int main() {
36
    int T;
37
    scanf("%d", &T);
38
    while (T--) {
39
        PLL p[4];
40
        for (int i = 0; i < 4; ++i) scanf("%lld%lld", &p[i].x, &p[i].y);
41
        int s1 = sign(area(p[0], p[1], p[2])), s2 = sign(area(p[0], p[1], p[3])), s3 = sign(area(p[2], p[3], p[0])), s4 = sign(area(p[2], p[3], p[1]));
42
        if (s1 == 0 && in_mid(p[0], p[1], p[2])) printf("YES\n");
43
        else if (s2 == 0 && in_mid(p[0], p[1], p[3])) printf("YES\n");
44
        else if (s3 == 0 && in_mid(p[2], p[3], p[0])) printf("YES\n");
45
        else if (s4 == 0 && in_mid(p[2], p[3], p[1])) printf("YES\n");
46
        else if (s1 != s2 && s3 != s4) printf("YES\n");
47
        else printf("NO\n");
48
    }
49
    return 0;
50
}

Polygon Area#

多边形面积，用三角剖分，取原点为参考点，按着边的顺序做叉积，求和取绝对值，这道题让求面积的二倍，所以不用除以二。

1
#include <iostream>
2
#define x first
3
#define y second
4
using namespace std;
5
typedef long long LL;
6
typedef pair<LL, LL> PLL;
7
const int N = 1010;
8

9
PLL operator -(PLL a, PLL b) {
10
    return {a.x - b.x, a.y - b.y};
11
}
12

13
LL operator *(PLL a, PLL b) {
14
    return a.x * b.y - a.y * b.x;
15
}
16

17
LL area(PLL a, PLL b, PLL c) {
18
    return (b - a) * (c - a);
19
}
20

21
PLL a[N];
22

23
int main() {
24
    int n;
25
    scanf("%d", &n);
26
    for (int i = 0; i < n; ++i) {
27
        scanf("%lld%lld", &a[i].x, &a[i].y);
28
    }
29
    a[n] = a[0];
30
    LL res = 0;
31
    for (int i = 0; i < n; ++i) {
32
        res += area({0, 0}, a[i], a[i + 1]);
33
    }
34
    printf("%lld\n", abs(res));
35
    return 0;
36
}

Point in Polygon#

特判在边界的情况，别的地方用射线法。

1
#include <iostream>
2
#include <cmath>
3
#include <vector>
4
#include <algorithm>
5
#define x first
6
#define y second
7
using namespace std;
8
typedef long long LL;
9
typedef pair<LL, LL> PLL;
10
const int N = 1010;
11

12
PLL operator -(PLL a, PLL b) {
13
    return {a.x - b.x, a.y - b.y};
14
}
15

16
LL operator *(PLL a, PLL b) {
17
    return a.x * b.y - a.y * b.x;
18
}
19

20
LL area(PLL a, PLL b, PLL c) {
21
    return (b - a) * (c - a);
22
}
23

24
int sign(LL n) {
25
    if (n == 0) return 0;
26
    else if (n > 0) return 1;
27
    else return -1;
28
}
29

30
bool on_mid(PLL a, PLL b, PLL c) {
31
    vector<PLL> v = {a, b, c};
32
    sort(v.begin(), v.end());
33
    return v[1] == c;
34
}
35

36
bool check_intersection(PLL p, PLL q, PLL a, PLL b) {
37
    return sign(area(p, q, a)) * sign(area(p, q, b)) < 0 && sign(area(a, b, p)) * sign(area(a, b, q)) < 0;
38
}
39

40
PLL a[N];
41

42
int main() {
43
    int n, m;
44
    scanf("%d%d", &n, &m);
45
    for (int i = 0; i < n; ++i) scanf("%lld%lld", &a[i].x, &a[i].y);
46
    a[n] = a[0];
47
    while (m--) {
48
        PLL p, q;
49
        long double theta = 0;
50
        scanf("%lld%lld", &p.x, &p.y);
51
        q = {1000000007, p.y + 1};
52
        bool f = false, g = false;
53
        for (int i = 0; i < n; ++i) {
54
            if ((a[i + 1] - a[i]) * (p - a[i]) == 0) {
55
                if (on_mid(a[i], a[i + 1], p)) {
56
                    f = true;
57
                    break;
58
                }
59
            }
60
            else {
61
                g ^= check_intersection(p, q, a[i], a[i + 1]);
62
            }
63
        }
64
        if (f) printf("BOUNDARY\n");
65
        else if (g) printf("INSIDE\n");
66
        else printf("OUTSIDE\n");
67
    }
68
    return 0;
69
}

Polygon Lattice Points#

Minimum Euclidean Distance#

…还没学到…

Convex Hull#

一个看着很简单的 Andrew 在 Acwing 和 CSES 连挂了两次……

上一次是下标填错 (used[st[tp--]] 写成了 used[tp--])，这一次是 while 写成 if 没发现。

1
#include <iostream>
2
#include <algorithm>
3
#define x first
4
#define y second
5
using namespace std;
6
typedef long long LL;
7
typedef pair<LL, LL> PLL;
8
const int N = 200010;
9
PLL a[N];
10
int st[N], tp;
11
bool used[N];
12

13
PLL operator -(PLL a, PLL b) {
14
    return {a.x - b.x, a.y - b.y};
15
}
16

17
LL operator *(PLL a, PLL b) {
18
    return a.x * b.y - a.y * b.x;
19
}
20

21
LL area(PLL a, PLL b, PLL c) {
22
    return (b - a) * (c - a);
23
}
24

25
int main() {
26
    int n;
27
    scanf("%d", &n);
28
    for (int i = 1; i <= n; ++i) {
29
        scanf("%lld%lld", &a[i].x, &a[i].y);
30
    }
31
    sort(a + 1, a + n + 1);
32
    for (int i = 1; i <= n; ++i) {
33
        while (tp >= 2 && area(a[st[tp - 1]], a[st[tp]], a[i]) < 0) used[st[tp--]] = false;
34
        st[++tp] = i;
35
        used[i] = true;
36
    }
37
    used[1] = false;
38
    for (int i = n - 1; i; --i) {
39
        if (used[i]) continue;
40
        while (tp >= 2 && area(a[st[tp - 1]], a[st[tp]], a[i]) < 0) tp--;
41
        st[++tp] = i;
42
    }
43
    printf("%d\n", tp - 1);
44
    for (int i = 1; i < tp; ++i) {
45
        printf("%lld %lld\n", a[st[i]].x, a[st[i]].y);
46
    }
47
    return 0;
48
}

Maximum Manhattan Distances#

这道比较简单，从训练赛到上海月赛遇到过很多次了，只和 x + y 和 x - y 的最值有关系。

1
#include <iostream>
2
#include <climits>
3

4
using namespace std;
5
typedef long long LL;
6

7
int main() {
8
    int n;
9
    scanf("%d", &n);
10
    LL mx1 = LLONG_MIN, mx2 = LLONG_MIN, mn1 = LLONG_MAX, mn2 = LLONG_MAX;
11
    while (n--) {
12
        LL x, y;
13
        scanf("%lld%lld", &x, &y);
14
        mx1 = max(mx1, x + y), mx2 = max(mx2, x - y), mn1 = min(mn1, x + y), mn2 = min(mn2, x - y);
15
        printf("%lld\n", max(mx1 - mn1, mx2 - mn2));
16
    }
17
    return 0;
18
}

All Manhattan Distances#

横纵坐标没什么大关系，可以拆开分别算，没什么难度，但是第一次爆 long long 了。

1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4
typedef long long LL;
5
const int N = 200010;
6
LL x[N], y[N];
7

8
void print(__int128_t x) {
9
    if (x == 0) return;
10
    print(x / 10);
11
    printf("%d", x % 10);
12
}
13

14
int main() {
15
    int n;
16
    scanf("%d", &n);
17
    for (int i = 1; i <= n; ++i) scanf("%llu%llu", &x[i], &y[i]);
18
    sort(x + 1, x + n + 1);
19
    sort(y + 1, y + n + 1);
20
    __int128_t sx = 0, sy = 0, res = 0;
21
    for (int i = 1; i <= n; ++i) {
22
        res += (__int128_t)x[i] * (i - 1) + (__int128_t)y[i] * (i - 1) - sx - sy;
23
        sx += x[i], sy += y[i];
24
    }
25
    if (res == 0) printf("0\n");
26
    else print(res), printf("\n");
27
    return 0;
28
}

Intersection Points#

分出来横线竖线，按照起点横坐标排序横线和竖线，枚举竖线，利用优先队列维护横坐标跨越当前竖线的横坐标的横线，用树状数组维护覆盖情况。

另外，反着做应该也行，入队出队的时候需要做区间加减，查询需要单点查询，可以用树状数组维护差分数组，好处是少开一个优先队列。

1
#include <iostream>
2
#include <queue>
3
#include <algorithm>
4
#define x first
5
#define y second
6
using namespace std;
7
typedef pair<int, int> pii;
8
const int N = 100010, M = 2000002;
9
int tr[M];
10
struct Line {
11
    pii s, t;
12

13
    bool operator <(const Line& _) const {
14
        return t.x > _.t.x;
15
    }
16
} a[N], b[N];
17
priority_queue<Line> q;
18

19
void add(int u, int t) {
20
    for (; u <= M; u += u & -u) {
21
        tr[u] += t;
22
    }
23
}
24

25
int query(int u) {
26
    int res = 0;
27
    for (; u; u -= u & -u) {
28
        res += tr[u];
29
    }
30
    return res;
31
}
32

33
int main() {
34
    int n, l1 = 0, l2 = 0;
35
    scanf("%d", &n);
36
    for (int i = 1; i <= n; ++i) {
37
        pii s, t;
38
        scanf("%d%d%d%d", &s.x, &s.y, &t.x, &t.y);
39
        s.x += M / 2, s.y += M / 2, t.x += M / 2, t.y += M / 2;
40
        if (s.x > t.x || s.y > t.y) swap(s, t); // 保证从左到右从上到下
41
        if (s.x == t.x) a[++l1] = {s, t};
42
        else b[++l2] = {s, t};
43
    }
44
    sort(a + 1, a + l1 + 1, [](Line a, Line b) { // 竖线排序
45
        return a.s.x < b.s.x;
46
    });
47
    sort(b + 1, b + l2 + 1, [](Line a, Line b) { // 横线排序
48
        return a.s.x < b.s.x;
49
    });
50
    long long res = 0;
51
    for (int i = 1, j = 0; i <= l1; ++i) {
52
        while (j + 1 <= l2 && b[j + 1].s.x <= a[i].s.x) {
53
            q.emplace(b[++j]);
54
            add(b[j].s.y, 1);
55
        }
56
        while (!q.empty() && q.top().t.x < a[i].s.x) {
57
            add(q.top().s.y, -1);
58
            q.pop();
59
        }
60
        res += query(a[i].t.y) - query(a[i].s.y - 1);
61
    }
62
    printf("%lld\n", res);
63
    return 0;
64
}

Line Segments Trace I#

这道题是半个半平面交，可以用单调栈维护，按照斜率不减的顺序排序。然后从左到右维护单调栈，保证交点横坐标单调递增。最终栈里面的就是最大值函数的边界，最终构成轮廓的几条直线在栈里的下标关于横坐标是单调的，所以输出答案的时候用双指针即可。

我因为单调栈的 if 条件太长打错了一个 first / second 卡了几十分钟……

1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4
typedef long long LL;
5
typedef pair<LL, LL> PLL;
6
const int N = 100010;
7
PLL a[N];
8
int st[N], tp;
9

10
LL calc(PLL line, int x) {
11
    return line.first + line.second * x;
12
}
13

14
int main() {
15
    int n, m;
16
    scanf("%d%d", &n, &m);
17
    for (int i = 1; i <= n; ++i) {
18
        LL y1, y2;
19
        scanf("%lld%lld", &y1, &y2);
20
        a[i] = {y1, (y2 - y1) / m};
21
    }
22
    sort(a + 1, a + n + 1, [](PLL a, PLL b) {
23
        return a.second == b.second ? a.first > b.first : a.second < b.second;
24
    });
25
    for (int i = 1; i <= n; ++i) {
26
        while (tp > 1 && (a[i].first - a[st[tp]].first) * (a[st[tp - 1]].second - a[st[tp]].second) <= (a[st[tp]].first - a[st[tp - 1]].first) * (a[st[tp]].second - a[i].second) || tp && a[i].first >= a[st[tp]].first) tp--;
27
        st[++tp] = i;
28
    }
29
    for (int i = 0, j = 1; i <= m; ++i) {
30
        while (j < tp && calc(a[st[j]], i) <= calc(a[st[j + 1]], i)) j++;
31
        printf("%lld ", calc(a[st[j]], i));
32
    }
33
    printf("\n");
34
    return 0;
35
}

Line Segments Trace II#

我学会李超树了！这道题是李超树的板子，李超树利用标记永久化解决了一个线段在不同位置最优性不同的问题。一般的线段树区间修改是找到目标区间直接改懒标记就行，李超树的区间修改的思想是保证当前的懒标记能让一半是最优的，然后用相同的条件递归另一半，这样单点查询的时候取一路的 max 一定能取到一次最优的线段。如果主席树比较熟看一眼代码就明白了。

1
#include <iostream>
2
using namespace std;
3
typedef long long LL;
4
typedef pair<LL, LL> PLL;
5
const int N = 100010;
6
PLL tr[N * 4];
7

8
LL get_val(PLL line, int x) {
9
    return line.first + line.second * x;
10
}
11

12
void modify(int u, int l, int r, int ql, int qr, PLL v) {
13
    if (l == r) {
14
        tr[u] = get_val(tr[u], l) > get_val(v, l) ? tr[u] : v;
15
    }
16
    else if (ql <= l && r <= qr) {
17
        int mid = l + r >> 1;
18
        if (get_val(v, mid) > get_val(tr[u], mid)) swap(tr[u], v);
19
        if (get_val(v, l) <= get_val(tr[u], l)) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
20
        else if (get_val(v, r) <= get_val(tr[u], r)) modify(u << 1, l, mid, ql, qr, v);
21
    }
22
    else {
23
        int mid = l + r >> 1;
24
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
25
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
26
    }
27
}
28

29
LL query(int u, int l, int r, int p) {
30
    if (l == r) return get_val(tr[u], l);
31
    else {
32
        int mid = l + r >> 1;
33
        if (p <= mid) return max(get_val(tr[u], p), query(u << 1, l, mid, p));
34
        else return max(get_val(tr[u], p), query(u << 1 | 1, mid + 1, r, p));
35
    }
36
}
37

38
int main() {
39
    ios::sync_with_stdio(0);
40
    cin.tie(0), cout.tie(0);
41
    int n, m;
42
    cin >> n >> m;
43
    fill(tr, tr + m * 4, make_pair(-1, 0));
44
    for (int i = 1; i <= n; ++i) {
45
        LL x1, y1, x2, y2;
46
        cin >> x1 >> y1 >> x2 >> y2;
47
        modify(1, 0, m, x1, x2, {(x1 * y2 - x2 * y1) / (x1 - x2), (y1 - y2) / (x1 - x2)});
48
    }
49
    for (int i = 0; i <= m; ++i) {
50
        cout << query(1, 0, m, i) << ' ';
51
    }
52
    cout << endl;
53
    return 0;
54
}

Lines and Queries I#

和上一道基本上一样，甚至还省了一个区间修改，只需要更新懒标记。需要注意函数值可能是负的了，需要初始化成负无穷。

1
#include <iostream>
2
using namespace std;
3
typedef long long LL;
4
typedef pair<LL, LL> PLL;
5
const int N = 100010;
6
PLL tr[N * 4];
7

8
LL get_val(PLL line, int x) {
9
    return line.first + line.second * x;
10
}
11

12
void modify(int u, int l, int r, int ql, int qr, PLL v) {
13
    if (l == r) {
14
        tr[u] = get_val(tr[u], l) > get_val(v, l) ? tr[u] : v;
15
    }
16
    else if (ql <= l && r <= qr) {
17
        int mid = l + r >> 1;
18
        if (get_val(v, mid) > get_val(tr[u], mid)) swap(tr[u], v);
19
        if (get_val(v, l) <= get_val(tr[u], l)) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
20
        else if (get_val(v, r) <= get_val(tr[u], r)) modify(u << 1, l, mid, ql, qr, v);
21
    }
22
    else {
23
        int mid = l + r >> 1;
24
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
25
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
26
    }
27
}
28

29
LL query(int u, int l, int r, int p) {
30
    if (l == r) return get_val(tr[u], l);
31
    else {
32
        int mid = l + r >> 1;
33
        if (p <= mid) return max(get_val(tr[u], p), query(u << 1, l, mid, p));
34
        else return max(get_val(tr[u], p), query(u << 1 | 1, mid + 1, r, p));
35
    }
36
}
37

38
int main() {
39
    ios::sync_with_stdio(0);
40
    cin.tie(0), cout.tie(0);
41
    int q, m = 100000;
42
    cin >> q;
43
    fill(tr, tr + m * 4, make_pair(-1000001000000000, 0));
44
    while (q--) {
45
        int op;
46
        cin >> op;
47
        if (op == 1) {
48
            LL a, b;
49
            cin >> a >> b;
50
            modify(1, 0, m, 0, m, {b, a});
51
        }
52
        else {
53
            int x;
54
            cin >> x;
55
            cout << query(1, 0, m, x) << endl;
56
        }
57
    }
58
    return 0;
59
}

Lines and Queries II#

在上一道的基础上把生效区间加回来了。

1
#include <iostream>
2
using namespace std;
3
typedef long long LL;
4
typedef pair<LL, LL> PLL;
5
const int N = 100010;
6
PLL tr[N * 4];
7

8
LL get_val(PLL line, int x) {
9
    return line.first + line.second * x;
10
}
11

12
void modify(int u, int l, int r, int ql, int qr, PLL v) {
13
    if (l == r) {
14
        tr[u] = get_val(tr[u], l) > get_val(v, l) ? tr[u] : v;
15
    }
16
    else if (ql <= l && r <= qr) {
17
        int mid = l + r >> 1;
18
        if (get_val(v, mid) > get_val(tr[u], mid)) swap(tr[u], v);
19
        if (get_val(v, l) <= get_val(tr[u], l)) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
20
        else if (get_val(v, r) <= get_val(tr[u], r)) modify(u << 1, l, mid, ql, qr, v);
21
    }
22
    else {
23
        int mid = l + r >> 1;
24
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
25
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
26
    }
27
}
28

29
LL query(int u, int l, int r, int p) {
30
    if (l == r) return get_val(tr[u], l);
31
    else {
32
        int mid = l + r >> 1;
33
        if (p <= mid) return max(get_val(tr[u], p), query(u << 1, l, mid, p));
34
        else return max(get_val(tr[u], p), query(u << 1 | 1, mid + 1, r, p));
35
    }
36
}
37

38
int main() {
39
    ios::sync_with_stdio(0);
40
    cin.tie(0), cout.tie(0);
41
    int q, m = 100000;
42
    cin >> q;
43
    fill(tr, tr + m * 4, make_pair(-1000001000000001, 0));
44
    while (q--) {
45
        int op;
46
        cin >> op;
47
        if (op == 1) {
48
            int a, b, l, r;
49
            cin >> a >> b >> l >> r;
50
            modify(1, 0, m, l, r, {b, a});
51
        }
52
        else {
53
            int x;
54
            cin >> x;
55
            LL res = query(1, 0, m, x);
56
            if (res == -1000001000000001) cout << "NO" << endl;
57
            else cout << res << endl;
58
        }
59
    }
60
    return 0;
61
}

Area of Rectangles#

NOTE
这道题看了题解，知道有一种用线段树的做法但是靠自己想没想出来怎么维护。

矩形面积并是一个经典的扫描线问题，可以想象成把这一堆矩形放到一块然后按照 $x = 0,-1,1,-2,2\dots$ 切成很多长条，这些长条的面积是很好计算的。暴力的做法可以参考 AcWing 做题记录。

我们需要从左到右扫一遍横坐标，然后想办法高效维护垂直于 x 轴方向上的覆盖长度。这涉及到区间加减和区间查询，所以第一个就可以想到线段树。但是如果要开线段树，要维护的一定得是某个 y 的区间被覆盖的次数，否则当一个矩形结束的时候你没有办法删掉，问题就在于如果维护的是被覆盖的次数那怎么统计有多少个位置是被覆盖的。这里用到了一个巧妙的转化，我们维护区间最小值和区间最小值的数量。

如果区间最小值是 0，那么被覆盖的次数就是区间长度 - 最小值0的个数
否则被覆盖的次数就是区间长度

可以发现这个状态是可以合并的，合并时只需要比较一下两个儿子最小值的大小，如果不相等，直接用较小的；否则把儿子的最小值个数相加。这道题坐标数量级只有 $10^6$ ，所以不用离散化了，直接暴力做的行了。

1
#include <iostream>
2
#include <tuple>
3
#include <vector>
4

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 2000010;
9

10
vector<tuple<int, int, int>> v[N];
11
struct Node {
12
    int val, len, tag;
13
} tr[N * 4];
14

15
void pushup(int u) {
16
    if (tr[u << 1].val == tr[u << 1 | 1].val) tr[u].val = tr[u << 1].val, tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
17
    else if (tr[u << 1].val < tr[u << 1 | 1].val) tr[u].val = tr[u << 1].val, tr[u].len = tr[u << 1].len;
18
    else tr[u].val = tr[u << 1 | 1].val, tr[u].len = tr[u << 1 | 1].len;
19
}
20

21
void build(int u, int l, int r) {
22
    if (l == r) tr[u] = {0, 1, 0};
23
    else {
24
        int mid = l + r >> 1;
25
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
26
        pushup(u);
27
    }
28
}
29

30
void pushdown(int u) {
31
    if (tr[u].tag) {
32
        tr[u << 1].tag += tr[u].tag, tr[u << 1 | 1].tag += tr[u].tag;
33
        tr[u << 1].val += tr[u].tag, tr[u << 1 | 1].val += tr[u].tag;
34
        tr[u].tag = 0;
35
    }
36
}
37

38
void modify(int u, int l, int r, int ql, int qr, int v) {
39
    if (ql <= l && r <= qr) {
40
        tr[u].val += v, tr[u].tag += v;
41
    }
42
    else {
43
        pushdown(u);
44
        int mid = l + r >> 1;
45
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
46
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
47
        pushup(u);
48
    }
49
}
50

51
int main() {
52
    ios::sync_with_stdio(0);
53
    cin.tie(0), cout.tie(0);
54
    int n, m = 2000001;
55
    cin >> n;
56
    for (int i = 1; i <= n; ++i) {
57
        int x1, y1, x2, y2;
58
        cin >> x1 >> y1 >> x2 >> y2;
59
        x1 += 1000001, x2 += 1000001, y1 += 1000001, y2 += 1000001;
60
        v[x1].emplace_back(1, y1, y2 - 1);
61
        v[x2].emplace_back(-1, y1, y2 - 1);
62
    }
63
    build(1, 1, m);
64
    LL res = 0;
65
    for (int i = 1; i <= m; ++i) {
66
        for (auto [f, l, r] : v[i]) modify(1, 1, m, l, r, f);
67
        res += tr[1].val == 0 ? m - tr[1].len : m;
68
    }
69
    cout << res << endl;
70
    return 0;
71
}