学步园

扫描线第一题,第一次交上去居然PE了,好吧,有傻逼了,少加个了个回车.

注意点:

1. 区间分段的时候要分成 [l,mid] 和[mid,r]不是平常一样的[l,mid]和[mid+1,r](因为我们要算的一段线段的长度,也就是说得连续,比如我们要算这一段[1,10],应该把他分成[1,5][5,10],不能[1,5][6,10]);

2.由于上面的mid和平时的线段树不同,所以判断退出的时候是(l+1==r)才退出,因为我们表示的是一段线段,每个值是一个点,如果l等于r的话,就是一个点了,也没意义了.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#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=100000+10;
int k;
class Line
{
    public:
    double x,yu,yd;
    int type;
    Line(){}
    Line(double a,double b,double c,int d) :x(a),yu(b),yd(c),type(d) {}
    bool operator <(const Line &a) const
    {
        return x<a.x;
    }
};
vector<Line> line;
vector<double> cor_y;
map<double,int> pj;
class SGtree
{
    public:
    double len[MAXN<<2];
    int cnt[MAXN<<2];
    void build(int idx,int l,int r)
    {
        len[idx]=cnt[idx]=0;
        if(l+1==r) return ;
        build(lson);
        build(rson);
    }
    void maintain(int idx,int l,int r)
    {
        if(cnt[idx]>0) len[idx]=cor_y[r]-cor_y[l];
        else
        {
            if(l+1==r) len[idx]=0;
            else len[idx]=len[lc]+len[rc];
        }
    }
    void update(int idx,int l,int r,int x,int y,int v)
    {
        if(x<=l && r<=y)
            cnt[idx]+=v;
        else
        {
            if(x<mid) update(lson,x,y,v);
            if(y>mid) update(rson,x,y,v);
        }
        maintain(whole);
    }
};
SGtree tree;
int main()
{
//    freopen("in","r",stdin);
    int n,kcase=1;
    while(~scanf("%d",&n) && n)
    {
        line.clear();
        cor_y.clear();
        pj.clear();
        double a,b,c,d;
        for(int i =0; i<n; i++)
        {
            scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
            line.push_back(Line(a,d,b,1));
            line.push_back(Line(c,d,b,-1));
            cor_y.push_back(b);
            cor_y.push_back(d);
        }
        cor_y.push_back(-100000000);
        sort(line.begin(),line.end());
        sort(cor_y.begin(),cor_y.end());
        k=1;
        for(int i=1; i<cor_y.size(); i++)
        {
            if(cor_y[i]!=cor_y[i-1])
            {
                pj[cor_y[i]]=k;
                cor_y[k++]=cor_y[i];
            }
        }
        double ans=0;
        tree.build(1,1,k-1);
        tree.update(1,1,k-1,pj[line[0].yd],pj[line[0].yu],line[0].type);
        for(int i=1; i<line.size(); i++)
        {
            ans+=(line[i].x-line[i-1].x)*(tree.len[1]);
            tree.update(1,1,k-1,pj[line[i].yd],pj[line[i].yu],line[i].type);
        }
        printf("Test case #%d\n",kcase++);
        printf("Total explored area: %.2f\n\n",ans) ;
    }
    return 0;
}