扫描线求面积和周长 （模板，线段树）

介绍

快速计算多个矩形覆盖区域的面积或者周长。

实现

求面积

oi_wiki的扫描线解释得很清楚了，就是求每次扫到得底边覆盖的长度乘上高的总和。
主要是代码实现的细节要注意。这里的线段树离散化处理记录一下。
HDU1542 - Atlantis

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

using namespace std;
#define endl '
'
typedef long long ll;

const int N = 3000;

struct snode {
    double x, y1, y2;
    int flag;
    
};

bool cmp(const snode &a, const snode &b) {
    return a.x < b.x;
}

struct tnode {
    double sum, l, r;
};

tnode st[N << 2];
snode seg[N];
double num[N];
int lazy[N << 2];

void pushup(int rt) {
    if(lazy[rt] > 0) {
        st[rt].sum = st[rt].r - st[rt].l;
    } else {
        st[rt].sum = st[rt << 1].sum + st[rt << 1 | 1].sum;
    }
}

void update(double L, double R, int rt, int flag) {
    if(L == st[rt].l && R == st[rt].r) {
        lazy[rt] += flag;
        pushup(rt);
        return ;
    }
    if(st[rt << 1].r > L) //>而不是>=？不能等于，否则区间长度为0，会进入死循环。
        update(L, min(R, st[rt << 1].r), rt << 1, flag);
    if(st[rt << 1 | 1].l < R) 
        update(max(L, st[rt << 1 | 1].l), R, rt << 1 | 1, flag);
    pushup(rt);
}

void build(int lef, int rig, int rt) {
    if(rig - lef > 1) { //由于mid公用，所以>1就可以
        int mid = (lef + rig) / 2;
        st[rt].l = num[lef]; //离散化
        st[rt].r = num[rig];
        build(lef, mid, rt << 1);
        build(mid, rig, rt << 1 | 1); //mid而不是mid+1？因为是线段，头尾需要相连，否则答案会少值
        pushup(rt);
    } else {
        st[rt].l = num[lef];
        st[rt].r = num[rig];
        st[rt].sum = 0;
    }
}


int main() {
    ios::sync_with_stdio(false);
    int n;
    int cases = 0;
    while(1) {
        scanf("%d", &n);
        if(!n) break;
        cases++;
        for(int i = 0; i < n; i++) {
            double x1, x2, y1, y2;
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            seg[i].x = x1; seg[i].y1 = y1; seg[i].y2 = y2; 
            seg[i].flag = 1;
            seg[i + n].x = x2; seg[i + n].y1 = y1; seg[i + n].y2 = y2; 
            seg[i + n].flag = -1;

            num[i + 1] = y1;
            num[i + 1 + n] = y2;
        }
        sort(num + 1, num + 1 + (2 * n)); //离散化
        sort(seg, seg + 2 * n, cmp);
        memset(lazy, 0, sizeof lazy);
        build(1, 2 * n, 1);
        double ans = 0;
        update(seg[0].y1, seg[0].y2, 1, seg[0].flag);
        for(int i = 1; i < 2 * n; i++) {
            ans += (seg[i].x - seg[i - 1].x) * st[1].sum;
            update(seg[i].y1, seg[i].y2, 1, seg[i].flag);
        }
        printf("Test case #%d
", cases);
        printf("Total explored area: %.2lf

", ans);
    }
}

求周长

周长可以先扫描x轴方向的，再扫描y轴方向的。
具体求法就是对每个线段，求线段覆盖前的总长减去线段覆盖后的总长的绝对值之和就是答案，画画图可得。
看了大佬们的博客，也有一次扫描就可以得到总周长的方法，有时间补上。
POJ1177 - Picture

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

using namespace std;
#define endl '
'
typedef long long ll;

const int N = 5001;

struct snode {
    int x, y1, y2;
    int flag;
    
};

bool cmp(const snode &a, const snode &b) {
    return a.x < b.x;
}

struct tnode {
    int sum, l, r;
};

int ran[N << 1][4];
tnode st[N << 3];
snode seg[N << 1];
int num[N << 1];
int lazy[N << 3];

void pushup(int rt) {
    if(lazy[rt] > 0) {
        st[rt].sum = st[rt].r - st[rt].l;
    } else {
        st[rt].sum = st[rt << 1].sum + st[rt << 1 | 1].sum;
    }
}

void update(int L, int R, int rt, int flag) {
    if(L == st[rt].l && R == st[rt].r) {
        lazy[rt] += flag;
        pushup(rt);
        return ;
    }
    if(st[rt << 1].r > L) //>而不是>=？不能等于，否则长度为0，会进入死循环。
        update(L, min(R, st[rt << 1].r), rt << 1, flag);
    if(st[rt << 1 | 1].l < R) 
        update(max(L, st[rt << 1 | 1].l), R, rt << 1 | 1, flag);
    pushup(rt);
}

void build(int lef, int rig, int rt) {
    if(rig - lef > 1) { //由于mid公用，所以>1就可以
        int mid = (lef + rig) / 2;
        st[rt].l = num[lef];
        st[rt].r = num[rig];
        build(lef, mid, rt << 1);
        build(mid, rig, rt << 1 | 1); //mid而不是mid+1？因为是线段，头尾需要相连，否则会少值
        pushup(rt);
    } else {
        st[rt].l = num[lef];
        st[rt].r = num[rig];
        st[rt].sum = 0;
    }
}


int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &ran[i][0], &ran[i][1], &ran[i][2], &ran[i][3]);
    }
    for(int i = 0; i < n; i++) {
        int x1 = ran[i][0], y1 = ran[i][1], x2 = ran[i][2], y2 = ran[i][3];
        seg[i].x = x1; seg[i].y1 = y1; seg[i].y2 = y2; 
        seg[i].flag = 1;
        seg[i + n].x = x2; seg[i + n].y1 = y1; seg[i + n].y2 = y2; 
        seg[i + n].flag = -1;
        num[i + 1] = y1;
        num[i + 1 + n] = y2;
    }
    sort(num + 1, num + 1 + (2 * n));
    sort(seg, seg + 2 * n, cmp);
    memset(lazy, 0, sizeof lazy);
    build(1, 2 * n, 1);
    int ans1 = 0;
    //update(seg[0].y1, seg[0].y2, 1, seg[0].flag);
    for(int i = 0; i < 2 * n; i++) {
        int t = st[1].sum;
        update(seg[i].y1, seg[i].y2, 1, seg[i].flag);
        ans1 += abs(st[1].sum - t);
        
    }

    for(int i = 0; i < n; i++) {
        int x1 = ran[i][0], y1 = ran[i][1], x2 = ran[i][2], y2 = ran[i][3];
        seg[i].x = y1; seg[i].y1 = x1; seg[i].y2 = x2; 
        seg[i].flag = 1;
        seg[i + n].x = y2; seg[i + n].y1 = x1; seg[i + n].y2 = x2; 
        seg[i + n].flag = -1;
        num[i + 1] = x1;
        num[i + 1 + n] = x2;
    }
    sort(num + 1, num + 1 + (2 * n));
    sort(seg, seg + 2 * n, cmp);
    memset(lazy, 0, sizeof lazy);
    build(1, 2 * n, 1);
    //update(seg[0].y1, seg[0].y2, 1, seg[0].flag);
    int ans2 = 0;
    for(int i = 0; i < 2 * n; i++) {
        int t = st[1].sum;
        update(seg[i].y1, seg[i].y2, 1, seg[i].flag);
        ans2 += abs(st[1].sum - t);
    }
    cout << ans1 + ans2 << endl;
}

update

为了防止计算周长时多计算一次y轴方向的长度，维护一个cnt代表每添加或删除一条边后有多少条线段，y轴方向的周长就是端点数乘上高的和。
由于我的代码的实现会产生长度为0的结点，所以在维护cnt的时候需要判断当前结点的子节点是否长度为0。

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

using namespace std;
#define endl '
'
typedef long long ll;

const int N = 7001; //多开一些空间，防止越界（好像是一些相等的情况越界）

struct snode {
    int x, y1, y2;
    int flag;
};

bool cmp(const snode &a, const snode &b) {
    return a.x < b.x;
}

struct tnode {
    int sum, l, r;
    bool rc, lc; //左右结点是否有值覆盖
    int cnt; //当前区间的线段数
};

int ran[N << 1][4];
tnode st[N << 3];
snode seg[N << 1];
int num[N << 1];
int lazy[N << 3];

int len(int rt) {return st[rt].r - st[rt].l;}

void pushup(int rt) {
    if(lazy[rt] > 0) {
        st[rt].sum = st[rt].r - st[rt].l;
        st[rt].cnt = 1;
        st[rt].lc = st[rt].rc = true;
    } else if(st[rt].l < st[rt].r) {
        st[rt].sum = st[rt << 1].sum + st[rt << 1 | 1].sum;
        st[rt].cnt = st[rt << 1].cnt + st[rt << 1 | 1].cnt - (st[rt << 1].rc & st[rt << 1 | 1].lc); //如果中间连起来了要删掉多余的部分
        if(len(rt << 1)) st[rt].lc = st[rt << 1].lc;
        else st[rt].lc = st[rt << 1 | 1].lc; //子结点长度为0的话，当前结点的信息取决于另一结点
        if(len(rt << 1 | 1)) st[rt].rc = st[rt << 1 | 1].rc;
        else st[rt].rc = st[rt << 1].rc;
    }
}

void update(int L, int R, int rt, int flag) {
    if(L == st[rt].l && R == st[rt].r) {
        lazy[rt] += flag;
        pushup(rt);
        return ;
    }
    if(st[rt << 1].r > L) //>而不是>=？不能等于，否则长度为0，会进入死循环。
        update(L, min(R, st[rt << 1].r), rt << 1, flag);
    if(st[rt << 1 | 1].l < R) 
        update(max(L, st[rt << 1 | 1].l), R, rt << 1 | 1, flag);
    pushup(rt);
}

void build(int lef, int rig, int rt) {
    if(rig - lef > 1) { //由于mid公用，所以>1就可以
        int mid = (lef + rig) / 2;
        st[rt].l = num[lef];
        st[rt].r = num[rig];
        build(lef, mid, rt << 1);
        build(mid, rig, rt << 1 | 1); //mid而不是mid+1？因为是线段，头尾需要相连，否则会少值
        pushup(rt);
    } else {
        st[rt].l = num[lef];
        st[rt].r = num[rig];
        st[rt].sum = 0;
        st[rt].lc = st[rt].rc = false;
        st[rt].cnt = 0;
    }
}



int arr[N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        seg[i].x = x1; seg[i].y1 = y1; seg[i].y2 = y2; 
        seg[i].flag = 1;
        seg[i + n].x = x2; seg[i + n].y1 = y1; seg[i + n].y2 = y2; 
        seg[i + n].flag = -1;
        num[i + 1] = y1;
        num[i + 1 + n] = y2;
    }
    sort(num + 1, num + 1 + (2 * n));
    sort(seg, seg + 2 * n, cmp);
    memset(lazy, 0, sizeof lazy);
    build(1, 2 * n, 1);
    int ans = 0;
    for(int i = 0; i < 2 * n; i++) {
        int t = st[1].sum;
        if(i > 0) {
            ans += 2 * st[1].cnt * (seg[i].x - seg[i - 1].x);
        }
        update(seg[i].y1, seg[i].y2, 1, seg[i].flag);
        ans += abs(st[1].sum - t);
    }
    cout << ans << endl;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/limil/p/12701921.html