题目描述

这是一道扫描线的题，提高课学习了扫描线的原理，但提高可那题太难写了，刚好看到这题就写它了；

算法1

参考文献

C++ 代码

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

using namespace std;

const int N = 10010;

int n;

struct Line{
    int x, y1, y2, tag;
    bool operator<(Line& b) 
    {
        return x < b.x;
    }
}lines[N * 2];

int idx;

struct Node{
    int l, r;
    int len;
    int cnt;
}tr[N * 8];

void pushup(int u)
{
    if(tr[u].cnt) tr[u].len = tr[u].r - tr[u].l + 1;
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)  return;
    else
    {
        int mid = (l + r) / 2;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int l, int r, int d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
       tr[u].cnt += d;
       pushup(u);
    }
    else
    {
        int mid = (tr[u].l + tr[u].r) / 2;
        if(l <= mid) modify(u << 1, l, r, d);
        if(r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

int query()
{
    return tr[1].len;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        y1 += 2, y2 += 2;
        lines[idx ++] = {x1, y1, y2, 1};
        lines[idx ++] = {x2, y1, y2, -1};
    }
    sort(lines, lines + idx);
    build(1, 1, N);
    int res = 0;
    int last = 0;
    for(int i = 0; i < idx; ++ i)
    {
        auto &v = lines[i];
        int k = query();
        res += k * (v.x - last);
        last = v.x;
        modify(1, v.y1, v.y2 - 1, v.tag);
    }
    printf("%d", res);
    return 0;
}