hdu 3265 Posters（线段树+扫描线+面积并）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3265

题意：给你一张挖了洞的墙纸贴在墙上，问你总面积有多少。

挖了洞后其实就是多了几个矩形墙纸，一张墙纸挖了洞后可以分成4个小矩形至于怎么分看个人喜好，然后再求个矩形的面积并

要注意的是x1==x3||x2==x4||y1==y3||y2==y4时不用分矩形这是个小小的优化。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int M = 5e4 + 10;
struct ss {
    int l , r , h , flag;
}s[M << 3];
struct TnT {
    int l , r , len , add;
}T[M << 3];
bool cmp(ss a , ss b) {
    return a.h < b.h;
}
void build(int l , int r , int p) {
    int mid = (l + r) >> 1;
    T[p].l = l , T[p].r = r , T[p].add = 0 , T[p].len = 0;
    if(l == r)
        return ;
    build(l , mid , p << 1);
    build(mid + 1 , r , (p << 1) | 1);
}
void pushup(int p) {
    if(T[p].add) {
        T[p].len = T[p].r - T[p].l + 1;
    }
    else if(T[p].l == T[p].r) {
        T[p].len = 0;
    }
    else {
        T[p].len = T[p << 1].len + T[(p << 1) | 1].len;
    }
}
void updata(int l , int r , int p , int ad) {
    int mid = (T[p].l + T[p].r) >> 1;
    if(T[p].l == l && T[p].r == r) {
        T[p].add += ad;
        pushup(p);
        return ;
    }
    if(mid >= r) {
        updata(l , r , p << 1 , ad);
    }
    else if(mid < l) {
        updata(l , r , (p << 1) | 1 , ad);
    }
    else {
        updata(l , mid , p << 1 , ad);
        updata(mid + 1 , r , (p << 1) | 1 , ad);
    }
    pushup(p);
}
int main() {
    int n;
    while(scanf("%d" , &n) != EOF) {
        if(n == 0)
            break;
        int gg = 0;
        int x1 , x2 , x3 , x4 , y1 , y2 , y3 , y4;
        int MAX = 0;
        for(int i = 1 ; i <= n ; i++) {
            scanf("%d%d%d%d%d%d%d%d" , &x1 , &y1 , &x2 , &y2 , &x3 , &y3 , &x4 , &y4);
            x1++ , x2++ , x3++ , x4++ , y1++ , y2++ , y3++ , y4++;
            MAX = max(max(max(x1 , x2) , max(x3 , x4)) , MAX);
            if(x1 != x3) {
                s[++gg].flag = -1;
                s[gg].l = x1;
                s[gg].r = x3;
                s[gg].h = y4;
                s[++gg].flag = 1;
                s[gg].l = x1;
                s[gg].r = x3;
                s[gg].h = y3;
            }
            if(x2 != x4) {
                s[++gg].flag = -1;
                s[gg].l = x4;
                s[gg].r = x2;
                s[gg].h = y4;
                s[++gg].flag = 1;
                s[gg].l = x4;
                s[gg].r = x2;
                s[gg].h = y3;
            }
            if(y1 != y3) {
                s[++gg].flag = -1;
                s[gg].l = x1;
                s[gg].r = x2;
                s[gg].h = y3;
                s[++gg].flag = 1;
                s[gg].l = x1;
                s[gg].r = x2;
                s[gg].h = y1;
            }
            if(y2 != y4) {
                s[++gg].flag = -1;
                s[gg].l = x1;
                s[gg].r = x2;
                s[gg].h = y2;
                s[++gg].flag = 1;
                s[gg].l = x1;
                s[gg].r = x2;
                s[gg].h = y4;
            }
        }
        sort(s + 1 , s + 1 + gg , cmp);
        build(1 , MAX , 1);
        int l , r;
        l = s[1].l;
        r = s[1].r - 1;
        updata(l , r , 1 , s[1].flag);
        long long area = 0;
        for(int i = 2 ; i <= gg ; i++) {
            area += (long long)T[1].len * (s[i].h - s[i - 1].h);
            l = s[i].l;
            r = s[i].r - 1;
            updata(l , r , 1 , s[i].flag);
        }
        printf("%lld
" , area);
    }
    return 0;
}