扫描线第二题

求周长

#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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

线段树

HDU 3275 Light

题意很简单 给你一串长度为n只有0,1的字符串,每次操作固定操作m长度 Read more…

线段树

HDU 1542 Atlantis

线段树扫描线入门题 扫描线扫描线 一开始看的时候真的是看的我整个人都不 Read more…

线段树

POJ 2777 Count Color 附带线段树小结

POJ 2777 题解 好久没这么兴奋过了 poj2777 这绝对是 Read more…