学步园

题目

用线段树来求矩形面积并

比照着其他人的代码，总算理解了。

先熟悉下，代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 220

struct Node
{
    int l,r;
    int c;
    double len;
}node[2000];

struct Line
{
    double x,y1,y2;
    int f;
}line[maxn];

bool cmp(Line a,Line b)
{
    return a.x<b.x;
}

double y[maxn];
int n,len;

void build(int l,int r,int rt)
{
    node[rt].l=l;
    node[rt].r=r;
    node[rt].len=0;
    node[rt].c=0;

    if(l+1==r) return;
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m,r,rt<<1|1);
}

void PushUp(int rt)
{
    if(node[rt].c>0){
        node[rt].len=y[node[rt].r]-y[node[rt].l];
    }
    else if(node[rt].l+1==node[rt].r)
        node[rt].len=0;
    else
        node[rt].len=node[rt<<1].len+node[rt<<1|1].len;
}

void update(int x,int y,int cov,int rt)
{
    int l,r;
    l=node[rt].l;
    r=node[rt].r;
    if(l>y||r<x) return ;
    if(l>=x&&r<=y){
        node[rt].c+=cov;
        PushUp(rt);
        return ;
    }
    update(x,y,cov,rt<<1);
    update(x,y,cov,rt<<1|1);
 /*   int m=(l+r)>>1;
    if(y<=m) update(x,y,cov,rt<<1);
    else if(x>=m) update(x,y,cov,rt<<1|1);
    else{
        update(x,m,cov,rt<<1);
        update(m,r,cov,rt<<1|1);
    } */
    PushUp(rt);
}

int BinarySearch(double val)
{
    int l=0,h=len,m;
    while(l<=h){
        m=(l+h)>>1;
        if(y[m]>val) h=m-1;
        else if(y[m]<val) l=m+1;
        else return m;
    }
    return l;
}

int main()
{
    int a,b,i,t,ncase=1;
    double ans,x1,x2,y1,y2;
    while(scanf("%d",&n),n){
        t=0;ans=0;
        for(i=0;i<n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].x=x1;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=1;
            y[t++]=y1;

            line[t].x=x2;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=-1;
            y[t++]=y2;
        }

        sort(y,y+t);

        len=unique(y,y+t)-y;
        len--;
        build(0,len,1);
        sort(line,line+t,cmp);

        printf("Test case #%d\n",ncase++);
        for(i=0;i<t-1;i++){
            a=BinarySearch(line[i].y1);
            b=BinarySearch(line[i].y2);
            update(a,b,line[i].f,1);
            ans+=node[1].len*(line[i+1].x-line[i].x);
        }
        printf("Total explored area: %0.2lf\n\n",ans);
    }
    return 0;
}