[日常摸鱼]poj1151Atlantis-扫描线

题意：给一堆长宽平行于坐标轴的长方形求并的面积

我个沙茶快写了一晚上…

大概思想就是先根据$y$坐标排个序，把$y$坐标离散化一下，放到线段树里面维护，这里的写法是让线段树的节点储存这个点对应的整段线段的信息，更新的时候如果不行就把线段拆开，以及注意一些细节（比如这里右孩子的区间是[mid,r]而不是[mid+1,r]因为下标其实应该是连续的实数）

我也讲不清楚了具体看代码…

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(register int i=1;i<=n;i++)
#define REP(i,a,b) for(register int i=a;i<=b;i++)
#define debug(x) printf("%s = %d\n",#x,x)
using namespace std;
typedef double dl;
const int N=;
struct tree
{
    dl l,r,s;int c;
}tr[N<<];
struct Line
{
    dl x,y1,y2;int f;
    Line(dl x=,dl y1=,dl y2=,int f=):x(x),y1(y1),y2(y2),f(f){}
}ls[N<<];
int T,n,cnt,tot;
dl y[N<<],ans,x1,x2,y1,y2;
inline bool operator <(Line a,Line b)
{
    return a.x<b.x;
}
#define lson (o<<1)
#define rson (o<<1|1)
inline void push_up(int o,int l,int r)
{
    if(tr[o].c>)
        tr[o].s=tr[o].r-tr[o].l;
    else if(l+==r)
        tr[o].s=;
    else
        tr[o].s=tr[lson].s+tr[rson].s;
}
inline void build(int o,int l,int r)
{
    tr[o].l=y[l];tr[o].r=y[r];
    if(l+==r)return;
    int mid=(l+r)>>;
    build(lson,l,mid);build(rson,mid,r);
}
inline void modify(int o,int l,int r,Line e)
{
    if(tr[o].l==e.y1&&tr[o].r==e.y2)
    {
        tr[o].c+=e.f;
        push_up(o,l,r);return;
    }int mid=(l+r)>>;
    if(e.y2<=tr[lson].r)modify(lson,l,mid,e);
    else if(e.y1>=tr[rson].l)modify(rson,mid,r,e);
    else
    {
        modify(lson,l,mid,Line(e.x,e.y1,tr[lson].r,e.f));
        modify(rson,mid,r,Line(e.x,tr[rson].l,e.y2,e.f));
    }
    push_up(o,l,r);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        rep(i,n)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            y[++cnt]=y1;y[++cnt]=y2;
            ls[++tot]=Line(x1,y1,y2,);ls[++tot]=Line(x2,y1,y2,-);
        }
        sort(y+,y+cnt+);sort(ls+,ls+tot+);
        build(,,cnt);modify(,,cnt,ls[]);
        REP(i,,tot)
        {
            ans+=(ls[i].x-ls[i-].x)*tr[].s;
            modify(,,cnt,ls[i]);
        }
        printf("Test case #%d\n",++T);
        printf("Total explored area: %.2lf\n\n",ans);
        ans=tot=cnt=;
    }
    return ;
}