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

hdu 3265 Posters(线段树,扫描线)

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

题意:给你n张矩形海报,之后每张矩形之中又挖去一个小矩形,问你n个复合矩形的面积并

思路:我们把那个挖空的小矩形变换一下,变成4个矩形

hdu 3265 Posters(线段树,扫描线)

就是这样,之后就变成了4个小矩形之后求一下面积并就好了

上代码吧:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define lson l, m , rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn = 50000+10;
struct Seg
{
    int r,l,h;
    int f;
    Seg(){};
    Seg(double a,double b,double c,int d) : l(a),r(b),h(c),f(d){}
    bool operator < (const Seg & cmp) const
    {
        return h < cmp.h;
    }
}edg[maxn<<3];
int X[maxn<<3];
struct node
{
    int len;
    int cnt;
}ve[maxn<<2];
void pushdown(int l,int r,int rt)
{
    if(ve[rt].cnt)
    {
        ve[rt].len = X[r+1] - X[l];
    }
    else if(l == r) ve[rt].len = 0;
    else
    {
        ve[rt].len = ve[rt<<1].len + ve[rt<<1|1].len;
    }
}
void update(int L,int R,int l,int r,int rt,int val)
{
//	cout<<l<<"   "<<r<<endl;
	if(L>R) return ;
    if(L<=l && R>=r)
    {
        ve[rt].cnt += val;
        pushdown(l,r,rt);
        return ;
    }
    int m = (r+l)>>1;
    if(L<=m)
    {
        update(L,R,lson,val);
    }
    if(R>m)
    {
        update(L,R,rson,val);
    }
    pushdown(l,r,rt);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int cnt = 0 ;
        int a1,b1,c1,d1,a2,b2,c2,d2;
        if(n == 0) break;
        for(int i = 0 ; i < n ;i++)
        {
            scanf("%d%d%d%d%d%d%d%d",&a1,&b1,&c1,&d1,&a2,&b2,&c2,&d2);
            X[cnt] = a1;
            edg[cnt++] = Seg(a1,c1,b1,1);
            X[cnt] = c1;
            edg[cnt++] = Seg(a1,c1,b2,-1);
            X[cnt] = a1;
            edg[cnt++] = Seg(a1,c1,d2,1);
            X[cnt] = c1;
            edg[cnt++] = Seg(a1,c1,d1,-1);
            X[cnt] = a1;
            edg[cnt++] =Seg(a1,a2,b2,1);
            X[cnt] = a2;
            edg[cnt++] = Seg(a1,a2,d2,-1);
            X[cnt] = c2;
            edg[cnt++] = Seg(c2,c1,b2,1);
            X[cnt] = c1;
            edg[cnt++] = Seg(c2,c1,d2,-1);
        }
        sort(X,X+cnt);
        sort(edg,edg+cnt);
        int m = unique(X,X+cnt) - X;
        long long ans = 0 ;
        for(int i = 0 ; i < cnt ; i++)
        {
            int l = lower_bound(X,X+m,edg[i].l) - X;
            int r = lower_bound(X,X+m,edg[i].r) - X -1;
            update(l,r,0,m,1,edg[i].f);
            ans += (long long)ve[1].len * (edg[i+1].h - edg[i].h);
        }
        printf("%lld\n",ans);
    }
}