学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1828

扫描线第二题,1A

思路:按照x轴和y轴各扫一次,也就是分两次计算,一次计算与x轴平行的周长 ,另一次与y轴,他们的和就是总周长.

每条边分左右两种边插进去线段树,线段树的cnt维护这个线段[l,r]已经被覆盖了多少次

1.如果左边线段覆盖 那么这一段上面全部+1;

2.如果右边 -1;

这样我们就知道在任意的区间有没有被覆盖过,被覆盖过了多少次;

1.当左边的边覆盖cnt为0的区域的时候,周长加上这段的没有被覆盖的长度

2.当右边的边减去覆盖,这时线段的cnt为1,减去后就变成0了,也就是出去的那条边的周长也要计算进去,所以答案也加上这段的长度;

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define lc idx<<1
#define rc idx<<1|1
#define mid ((l+r)>>1)
#define lson lc,l,mid
#define rson rc,mid,r
#define whole idx,l,r
using namespace std;
const int MAXN=10000*2+2;
struct Scanline
{
    int x,yu,yd,v;
    Scanline(){}
    Scanline(int xx,int yy,int yyyy,int vv) :x(xx),yu(yy),yd(yyyy),v(vv) {}
    bool operator <(const Scanline &a) const
    {
        return x<a.x;
    }
};
vector<Scanline> a,b;
class SGtree
{
private:
        int cnt[MAXN<<2];
public:
    void build(int idx,int l,int r)
    {
        cnt[idx]=0;
        if(l+1==r) return ;
        build(lson);
        build(rson);
    }
    void PushDown(int idx,int l,int r)
    {
        if(cnt[idx]!=-1)
        {
            cnt[lc]=cnt[rc]=cnt[idx];
            cnt[idx]=-1;
        }
    }
    int update(int idx,int l,int r,int x,int y,int v)
    {
        int ret=0;
        if(x<=l && r<=y && cnt[idx]!=-1)
        {
            cnt[idx]+=v;
            if(cnt[idx]==0 || (v==1 && cnt[idx]==1))
                return r-l;
        }
        else
        {
            PushDown(whole);
            if(x<mid) ret+=update(lson,x,y,v);
            if(y>mid) ret+=update(rson,x,y,v);
        }
        return ret;
    }
};
int n;
SGtree tree;
int sumup(vector<Scanline> &a)
{
    sort(a.begin(),a.end());
    int ret=0;
    tree.build(1,1,MAXN);
    for(int i=0;i<a.size();i++)
    {
        Scanline x=a[i];
        int p=tree.update(1,1,MAXN,x.yd,x.yu,x.v);
        ret+=p;
    }
    return ret;
}
int main()
{
    while(~scanf("%d",&n))
    {
        a.clear();
        b.clear();
        int x1,y1,x2,y2;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            x1+=10000;
            y1+=10000;
            x2+=10000;
            y2+=10000;
            a.push_back(Scanline(x1,y2,y1,1));
            a.push_back(Scanline(x2,y2,y1,-1));
            b.push_back(Scanline(y1,x2,x1,1));
            b.push_back(Scanline(y2,x2,x1,-1));
        }
        int ans=0;
        ans+=sumup(a);
        ans+=sumup(b);
        printf("%d\n",ans);
    }
    return 0;
}