1. 题目

传送门=￣ω￣=
题目大意：给出 n 个矩形（矩形顶点左边可能为小数）1<=n<=100，求这些矩形覆盖的面积大小（多次覆盖同一个地方只算一次覆盖），即求这些矩形的面积并。含多组数据

2. 题解

首先听说数据比较水，不用线段树直接暴力数组搞也能过。

其次看到网上有一部分智障写的什么鬼线段树。。。
智障云者，我向来是这样想，这样说，现在却有些踌躇了。——某树人
他们写的线段树只有递归到叶子节点才返回。这不就是常数巨大的数组吗？还一堆评论学习了学习了。。。误人子弟。

正解：扫描线+线段树+离散化

对于每个矩形，我们保存它的上边和下边，并且对这些边的左右端点的横坐标进行离散化，然后哈希这些横坐标。

我们的“扫描线”从下向上扫描，遇到一条下边，则让线段树上这条下边所对应的区间的被覆盖次数+1。如果遇到一条上边，则让线段树上这条下边所对应的区间的被覆盖次数-1。一个区间，如果它被覆盖次数>0，那么它所对应的被覆盖长度就是该区间长度（即这是个连续的区间）。如果它被覆盖次数=0，那么它所对应的被覆盖长度为它的线段树上的左儿子区间被覆盖长度+右儿子区间被覆盖长度。不可能出现覆盖次数<0 的情况，为什么呢？自己想想吧。因为不可能有两个上边对应同一个下边。

我们保存上一条边的纵坐标 last，每次答案加上 (当前的边的纵坐标-last)×总区间的被覆盖长度长度。

最后输出答案即可。

还有线段树要注意不是给坐标编号，而是给坐标之间的线段编号。

讲的不是很清楚（时间不够啦！）。具体扫描线的思想的话会后面再搞一个【算法】扫描线的博客的。这里空间太小写不下。

代码：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
int n,n2,cnt;
double h[205],lst,ans;
struct edge{double x1,x2,y;bool st;}e[205];
bool cmp(edge a,edge b){return a.y<b.y;}
struct N{int s,l,r;double len;}t[1005];
void build(int l,int r,int a)
{
    t[a].l=l,t[a].r=r,t[a].len=t[a].s=0;
    if(l==r)return;
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a));
}
void pup(int a)
{
    if(t[a].s)t[a].len=h[t[a].r+1]-h[t[a].l];
    else if(t[a].l==t[a].r)t[a].len=0;
    else t[a].len=t[LS(a)].len+t[RS(a)].len;
}
void update(double l,double r,int d,int a)
{
    if(l<=h[t[a].l]&&h[t[a].r+1]<=r){t[a].s+=d,pup(a);return;}
    if(l<h[t[LS(a)].r+1])update(l,r,d,LS(a));
    if(r>h[t[RS(a)].l])update(l,r,d,RS(a));
    pup(a);
}
int main()
{
    int T=0;
    while(scanf("%d",&n),n)
    {
        ans=cnt=0,T++,memset(h,-127,sizeof(h));
        double x1,y1,x2,y2;n2=n<<1;
        for(int i=1;i<=n2;i+=2)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            e[i].x1=x1,e[i].x2=x2,e[i].y=y1,e[i].st=1;
            e[i+1].x1=x1,e[i+1].x2=x2,e[i+1].y=y2,e[i+1].st=0;
            h[i]=x1,h[i+1]=x2;
        }
        sort(h+1,h+1+n2),sort(e+1,e+1+n2,cmp);
        for(int i=1;i<=n2;i++)if(h[i]!=h[i-1])h[++cnt]=h[i];
        build(1,cnt-1,1),lst=e[1].y;
        for(int i=1;i<=n2;i++)
        {
            ans+=(e[i].y-lst)*t[1].len,lst=e[i].y;
            if(e[i].st)update(e[i].x1,e[i].x2,1,1);
            else update(e[i].x1,e[i].x2,-1,1);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",T,ans);
    }
    return 0;
}