学步园

题目链接：http://poj.org/problem?id=1151

题目大意：

给出一些矩形，矩形之间可能重叠。

求覆盖的总面积

算法：

矩形面积并的典型应用。

我是把X坐标离散化

把线段树的每个节点代表它前面那个坐标到它这个坐标之间的线段。

然后把Y坐标用扫描线扫过，

根据当前有多少长度的X坐标被覆盖，

再乘以两个Y坐标之差。

代码如下：

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN=3000;
double tr[MAXN<<2];
int cot[MAXN<<2];
vector<double>hash;
vector<pair<pair<double,int>,pair<double,double> > >a;

bool cmp(const pair<pair<double,int>,pair<double,double> >& a, const pair<pair<double,int>,pair<double,double> >& b)
{
    return a.first.first<b.first.first;
}

void pushup(int rt, int l, int r)
{
    if(cot[rt])
    {
        tr[rt]=hash[r+1]-hash[l];
    }
    else if(l==r)
    {
        tr[rt]=0.0;
    }
    else
    {
        tr[rt]=tr[rt<<1]+tr[rt<<1|1];
    }
}

void update(double L, double R, int x, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        cot[rt]+=x;
        pushup(rt,l,r);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
    {
        update(L,R,x,l,mid,rt<<1);
    }
    if(R>mid)
    {
        update(L,R,x,mid+1,r,rt<<1|1);
    }
    pushup(rt,l,r);
}

int main()
{
    int n;
    int cas=1;
    while(scanf("%d",&n)==1&&n)
    {
        hash.clear();
        a.clear();
        memset(tr,0,sizeof(tr));
        memset(cot,0,sizeof(cot));
        for(int i=0; i<n; i++)
        {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            hash.push_back(x1);
            hash.push_back(x2);
            a.push_back(make_pair(make_pair(y1,1),make_pair(x1,x2)));
            a.push_back(make_pair(make_pair(y2,-1),make_pair(x1,x2)));
        }
        sort(a.begin(),a.end(),cmp);
        sort(hash.begin(),hash.end());
        hash.erase(unique(hash.begin(),hash.end()),hash.end());
        double ans=0.0;
        int m=hash.size();
        for(int i=0; i<2*n-1; i++)
        {
            int l=lower_bound(hash.begin(),hash.end(),a[i].second.first)-hash.begin();
            int r=lower_bound(hash.begin(),hash.end(),a[i].second.second)-hash.begin();
            if(l<r)
            {
                update(l,r-1,a[i].first.second,0,m-1,1);
            }
            ans+=(a[i+1].first.first-a[i].first.first)*(tr[1]);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",cas++,ans);//使用%.2lf会WA
    }
    return 0;
}