欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu3265Posters(线段树+离散化+扫描线详解 )

程序员文章站 2022-07-13 11:03:01
...

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

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

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

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

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

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

hdu3265Posters(线段树+离散化+扫描线详解 )

注意:此题数据较大!!最后的面积要用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;
}