【笔记】扫描线

Part 1 简介

扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长等问题。

Part 2 应用

Atlantis 问题

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

Part 3 代码实现

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

#define MAX_N 1000005
using namespace std;

long long lazy[MAX_N << 3];  //标记这条线段出现的次数
long long s[MAX_N << 3];
long long n;
long long ans;

struct Segment_tree {
    long long l, r;
    long long sum;
} tree[MAX_N << 3];  //线段树

struct node {
    long long x, y_1, y_2;
    long long flag;  //flag表示该边是矩形的左边界或右边界
} p[MAX_N << 3];     //坐标

inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

//定义sort比较
bool cmp(node a, node b) { return a.x < b.x; }

//上传
void pushup(int k) {
    if (lazy[k] > 0)
        tree[k].sum = tree[k].r - tree[k].l;
    else
        tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;
}

//建树
void build(long long k, long long l, long long r) {
    if (r - l > 1) {
        tree[k].l = s[l];
        tree[k].r = s[r];
        build(k << 1, l, (l + r) >> 1);
        build(k << 1 | 1, (l + r) >> 1, r);
        pushup(k);
    } else {
        tree[k].l = s[l];
        tree[k].r = s[r];
        tree[k].sum = 0;
    }
    return;
}

//更新
void update(long long k, long long y_1, long long y_2, long long flag) {
    if (tree[k].l == y_1 && tree[k].r == y_2) {
        lazy[k] += flag;
        pushup(k);
        return;
    } else {
        if (tree[k << 1].r > y_1) update(k << 1, y_1, min(tree[k << 1].r, y_2), flag);
        if (tree[k << 1 | 1].l < y_2) update(k << 1 | 1, max(tree[k << 1 | 1].l, y_1), y_2, flag);
        pushup(k);
    }
}

int main() {
    long long x_1, y_1, x_2, y_2;
    n = read();
    for (int i = 0; i < n; i++) {
        x_1 = read();
        y_1 = read();
        x_2 = read();
        y_2 = read();
        p[i].x = x_1;
        p[i].y_1 = y_1;
        p[i].y_2 = y_2;
        p[i].flag = 1;
        p[i + n].x = x_2;
        p[i + n].y_1 = y_1;
        p[i + n].y_2 = y_2;
        p[i + n].flag = -1;
        s[i + 1] = y_1;
        s[i + n + 1] = y_2;
    }
    sort(s + 1, s + (n << 1 | 1));  //离散化
    sort(p, p + (n << 1), cmp);     //把矩形的边的纵坐标从小到大排序
    build(1, 1, n << 1);            //建树
    memset(lazy, 0, sizeof(lazy));
    update(1, p[0].y_1, p[0].y_2, p[0].flag);
    for (int i = 1; i < (n << 1); i++) {
        ans += (p[i].x - p[i - 1].x) * tree[1].sum;
        update(1, p[i].y_1, p[i].y_2, p[i].flag);
    }
    printf("%lld\n", ans);

    return 0;
}

参考：

​ 扫描线 - OI Wiki