hdu3265Posters（线段树+离散化+扫描线详解 ）

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

此题是hdu1542求面积的变形，没做过的可以看下我之前写的博客 ：http://blog.csdn.net/qq_36782366/article/details/75209119

题目：现在有一些海报，但是这些海报中有一个矩形的洞

n张海报，给出海报以及每张海报上矩形洞的左下角和右上角的坐标 求最后的总面积

思路;此题可以转化为hdu1542的矩形求面积问题

一张有洞的海报可以看作是四张矩形的海报！！

注意：此题数据较大！！最后的面积要用long long！！！

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn =  401000;
int cnt[maxn];//记录某个区间的下底边个数
long long   sum[maxn];//记录某个区间的下底边总长度
int  X[maxn];//对x进行离散化,否则x为浮点数且很大无法进行线段树
//以横坐标作为线段(区间),对横坐标线段进行扫描
//扫描的作用是每次更新下底边总长度和下底边个数,增加新面积
struct Seg
{
    int  h , l , r;
    int s;
    Seg(){}
    Seg(int  a,int  b,int  c,int d) : l(a) , r(b) , h(c) , s(d) {}
    bool operator < (const Seg &cmp) const
    {
        return h < cmp.h;
    }
}ss[800000];
void PushUp(int rt,int l,int r) {
    if (cnt[rt])
        sum[rt] = X[r+1] - X[l];//需要理解 //表示该区间整个线段长度可以作为底边
    else if(l == r)
        sum[rt] = 0;
    else
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if (L <= l && r <= R)//该区间是当前扫描线段的一部分,则该区间下底边总长以及上下底边个数差更新
    {
        cnt[rt] += c;//这个位置的边的条数  如果大于0时需要计入底边
        PushUp(rt , l , r);//更新底边长
        return ;
    }
    int m = (l + r) >> 1;
    if (L <= m)
        update(L , R , c , lson);
    if (m < R)
        update(L , R , c , rson);
    PushUp(rt , l , r);
}
int main()
{
    int n ;
    while (~scanf("%d",&n) && n)
    {
        int m = 0;
        while (n --)
        {
            int  x1,x2,x3,x4,y1,y2,y3,y4;
            scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
            X[m] = x1;
            ss[m++] = Seg(x1 , x3 , y1 , 1);
            X[m] = x3;
            ss[m++] = Seg(x1 , x3 , y2 ,-1);

            X[m] = x3;
            ss[m++] = Seg(x3 , x4 , y1 , 1);
            X[m] = x4;
            ss[m++] = Seg(x3 , x4 , y3 , -1);

            X[m] = x3;
            ss[m++] = Seg(x3 , x4 , y4, 1);
            X[m] = x4;
            ss[m++] = Seg(x3 , x4 , y2 , -1);

            X[m] = x4;
            ss[m++] = Seg(x4 , x2 , y1 , 1);
            X[m] = x2;
            ss[m++] = Seg(x4 , x2 , y2 , -1);
        }
        sort(X , X + m);
        sort(ss , ss + m);
        int k = unique(X,X+m)-X;
        memset(cnt , 0 , sizeof(cnt));
        memset(sum , 0 , sizeof(sum));
        long long ret = 0;
        for (int i = 0 ; i < m - 1 ; i ++)
        {
            int l=lower_bound(X,X+k,ss[i].l)-X;
            int r=lower_bound(X,X+k,ss[i].r)-X-1;
            if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);//扫描线段时更新底边长度和底边相差个数
                ret +=(long long ) sum[1] * (ss[i+1].h - ss[i].h);//底乘以高
        }
        printf("%lld\n" ,ret);
    }
    return 0;
}