【学习笔记】扫描线

bilibili:BV1Mm411D7kr

讲了一下。

模板代码：

面积并：

#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

namespace IO
{
    template<typename T>
    T read(T x)
    {
        T sum = 0, opt = 1;
        char ch = getchar();
        while(!isdigit(ch)) opt = (ch == '-') ? -1 : 1, ch = getchar();
        while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
        return sum * opt;
    }
}
#define read IO::read(0)

const int N = 1e5 + 5;

int n;
int x[N << 1];
int ans;

struct Segment_Tree
{
    struct Node{
        int l, r, len, sum;
    }tr[N << 4];

    void push_up(int u)
    {
        if(tr[u].sum){
            tr[u].len = x[tr[u].r + 1] - x[tr[u].l];
        }
        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 ;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
    void update(int u, int l, int r, int c)
    {
        if(r <= x[tr[u].l] || x[tr[u].r + 1] <= l) return ;
        if(l <= x[tr[u].l] && x[tr[u].r + 1] <= r) {
            tr[u].sum += c;
            push_up(u);
            return ;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        update(u << 1, l, r, c);
        update(u << 1 | 1, l, r, c);
        push_up(u);
    }
}seg;

struct node
{
    int l, r, h, mark;
}line[N << 1];

inline bool cmp(node a, node b)
{
    return a.h < b.h;
}

void work()
{
    n = read;
    for(int i = 1;i <= n;i ++ ){
        int x1 = read, y1 = read, x2 = read, y2 = read;

        x[i * 2 - 1] = x1, x[i * 2] = x2;
        line[i * 2 - 1] = {x1, x2, y1, 1};
        line[i * 2] = {x1, x2, y2, -1};
    }    
    n <<= 1;
    sort(x + 1, x + 1 + n);
    sort(line + 1, line + 1 + n, cmp);

    int len = unique(x + 1,x + 1 + n) - x - 1;

    seg.build(1, 1, len - 1);

    for(int i = 1;i < n;i ++ ){
        seg.update(1, line[i].l, line[i].r, line[i].mark);
        ans += seg.tr[1].len * (line[i + 1].h - line[i].h);
    }
    cout << ans << endl;

}

signed main()
{
    int T = 1;
    while(T -- ) work();
    return 0;
}

周长并：

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

using namespace std;

namespace IO
{
    template<typename T>
    T read(T x)
    {
        T sum = 0, opt = 1;
        char ch = getchar();
        while(!isdigit(ch)) opt = (ch == '-') ? -1 : 1, ch = getchar();
        while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
        return sum * opt;
    }
}
#define read IO::read(0)
int ans;

const int N = 1e5 + 5;
int x[N << 1];
struct Segment_Tree
{
    struct Node
    {
        int l, r, sum, len, c;
        bool el, er;
    }tr[N << 4];

    void push_up(int u)
    {
        if(tr[u].sum){
            tr[u].len = x[tr[u].r + 1] - x[tr[u].l];
            tr[u].el = tr[u].er = true;
            tr[u].c = 1;
        }
        else{
            tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
            tr[u].el = tr[u << 1].el;
            tr[u].er = tr[u << 1 | 1].er;
            tr[u].c = tr[u << 1].c + tr[u << 1 | 1].c;
            if(tr[u << 1].er && tr[u << 1 | 1].el) {
                tr[u].c -= 1;
            }
        }
    }

    void build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, 0, 0, false, false};
        if(l == r) return ;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    void update(int u, int l, int r, int c)
    {
        if(r <= x[tr[u].l] || x[tr[u].r + 1] <= l) return ;
        if(l <= x[tr[u].l] && x[tr[u].r + 1] <= r) {
            tr[u].sum += c;
            push_up(u);
            return ;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        update(u << 1, l, r, c);
        update(u << 1 | 1, l, r, c);
        push_up(u);
    }
}seg;

struct node{
    int l, r, h, mark;
}line[N << 1];

bool cmp(node a, node b)
{
    if(a.h == b.h) return a.mark > b.mark;
    return a.h < b.h;
}
void work()
{
    int n = read;
    for(int i = 1;i <= n;i ++ ){
        int x1 = read, y1 = read, x2 = read, y2 = read;
        x[i * 2 - 1] = x1, x[i * 2] = x2;
        line[i * 2 - 1] = {x1, x2, y1, 1};
        line[i * 2] = {x1, x2, y2, -1};
    }
    n <<= 1;
    sort(x + 1, x + 1 + n);
    sort(line + 1, line + 1 + n, cmp);

    int len = unique(x + 1,x + 1 + n) - x - 1;
    seg.build(1, 1, len - 1);
    int last = 0;
    for(int i = 1;i < n;i ++ ){
        seg.update(1, line[i].l, line[i].r, line[i].mark);
        ans += 2 * (line[i + 1].h - line[i].h) * seg.tr[1].c;
        ans += abs(last - seg.tr[1].len);
        last = seg.tr[1].len;
    }
    ans += line[n].r - line[n].l;
    cout << ans << endl;
}

int main()
{
    int T = 1;
    while(T -- ) work();
    return 0;
}