HDU 1828 Picture

扫描线第二题

求周长

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

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=20010;
int sum[maxn<<2],segnum[maxn<<2],flag[maxn<<2];//sum与上面一样   segnum记录未被覆盖的竖边数量   flag 同上
bool lseg[maxn<<2],rseg[maxn<<2];////表示某个区间最左边和最右边是否有下底边多于上底边
struct node
{
    int lx,rx;
    int y,d;
    node(){}
    node(int _lx,int _rx,int _y,int _d)
    {
        lx=_lx,rx=_rx,y=_y,d=_d;
    }
    bool operator <(const node& a)const
    {
        if(y==a.y) return d>a.d;
        return y<a.y;
    }
}lines[maxn];

void pushup(int id,int le,int ri)
{
    if(flag[id])
    {
        sum[id]=ri-le+1;
        lseg[id]=rseg[id]=true;
        segnum[id]=2;
    }
    else if(le==ri) sum[id]=lseg[id]=rseg[id]=segnum[id]=0;
    else
    {
        sum[id]=sum[id<<1]+sum[id<<1|1];
        segnum[id]=segnum[id<<1]+segnum[id<<1|1];
        lseg[id]=lseg[id<<1];
        rseg[id]=rseg[id<<1|1];
        if(rseg[id<<1]&&lseg[id<<1|1]) segnum[id]-=2;//矩形相交
    }
}

void update(int id,int le,int ri,int st,int en,int add)
{
    if(st<=le&&ri<=en)
    {
        flag[id]+=add;
        pushup(id,le,ri);
        return ;
    }
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid,st,en,add);
    if(en>mid) update(id<<1|1,mid+1,ri,st,en,add);
    pushup(id,le,ri);
}

int main()
{
    int n,x1,y1,x2,y2;
    while(scanf("%d",&n)!=EOF)
    {
        int ss=inf,ee=-inf;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            lines[2*i+1]=node(x1,x2,y1,1);
            lines[2*i+2]=node(x1,x2,y2,-1);
            ss=min(x1,ss),ee=max(x2,ee);
        }
        n*=2;
        sort(lines+1,lines+1+n);
        int ans=0,last=0;
        for(int i=1;i<=n;i++)
        {
            update(1,ss,ee,lines[i].lx,lines[i].rx-1,lines[i].d);
            ans+=segnum[1]*(lines[i+1].y-lines[i].y);
            ans+=abs(sum[1]-last);//底边增加的长度
            last=sum[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}