Atlantis

题意：
给定平面直角坐标系中的个矩形，求它们的面积并，即这些矩形的并集在坐标系中覆盖的总面积。
输入
接着输入行，每行输入表示矩形的左下角、右下角顶点坐标，这些坐标不一定是整数。

用一条竖直直线从左到右扫过整个坐标系，那么直线上被并集图形覆盖的长度只会在矩形的左右边界出发生变化(废话)。也就是说，整个并集图形可以被分成段，每一段在直线上的长度(记为)是固定的，因此该段的面积就是该段的宽度，各段面积之和即为所求。这些直线被称为扫描线，这种解题思路被称为扫描线法。

取出个矩形的左右边界作为扫描线(又是废话)，若一个矩形的左下角角顶点为、右下角顶点为，那么左右边界分别是四元组。Stars in Your Window中已经讲过这么处理的原因，不在累赘。

假设有个不同的纵坐标，那么扫描线最多被分成个段(我们需要的是段的长度，一个“点”是没有意义的)，每一段被覆盖的次数是，我们需要知道每个扫描线上的段的长度之和。

就相当于给你一个数组，每个下标对应一个权值，时权值才有效，每次操作数组的一个区间加一或者减一，动态维护，这个我现在只会的模拟。

但是这题有所不同，它的区间加和区间减都是成对出现的，所以我只要记录线段树某个节点代表的区间被矩形覆盖的次数，以及被覆盖的长度，同时没必要往下传懒标记，只需要在更新时稍微改变一下做法，若某个节点代表的区间被覆盖过，那么等于区间长度，否则等于两个子树的区间长度之和。

对于一个四元组，因为线段树维护的是段长度之和所以修改的对象应该是段，第段其实就是(表示第大的纵坐标)，那么我们就应该在线段树的区间上执行修改。

最后，纵坐标离散化肯定是要的，然后代码肯定和思路不太一样。

MyCode:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=2e2+7,maxE=8e2+7;
typedef long long int ll;
struct node {
    double x,l,r;
    int val;
    bool operator<(const node& a)const {
        return x<a.x;
    }
} q[maxn];
int cnt[maxE];
double b[maxn],raw[maxn],len[maxE];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline void pushup(int l,int r,int rt) {
    if(cnt[rt]) len[rt]=raw[r+1]-raw[l];
    else if(l==r) len[rt]=0.0;
    else len[rt]=len[rt<<1]+len[rt<<1|1];
}
inline void update(int x,int y,ll val,int l,int r,int rt) {
    if(x<=l&&r<=y) {
        cnt[rt]+=val;
        pushup(l,r,rt);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(x,y,val,lson);
    if(y>mid) update(x,y,val,rson);
    pushup(l,r,rt);
}
int main() {
    int n,tot,cas=0;
    while(scanf("%d",&n)&&n) {
        tot=0;
        memset(len,0,sizeof len);
        memset(cnt,0,sizeof cnt);
        for(int i=1,x,y,c; i<=n; ++i) {
            double x1,x2,y1,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            q[++tot]=node {x1,y1,y2,1};
            b[tot]=y1;
            q[++tot]=node {x2,y1,y2,-1};
            b[tot]=y2;
        }
        sort(b+1,b+1+tot);
        int mm=unique(b+1,b+1+tot)-b;
        for(int i=1,tmp; i<=tot; i+=2) {
            tmp=lower_bound(b+1,b+mm,q[i].l)-b;
            raw[tmp]=q[i].l;
            q[i].l=q[i+1].l=tmp;
            tmp=lower_bound(b+1,b+mm,q[i].r)-b;
            raw[tmp]=q[i].r;
            q[i].r=q[i+1].r=tmp;
        }
        sort(q+1,q+1+tot);
        double ans=0.0;
        mm-=1;
        update(q[1].l,q[1].r-1,1,1,mm,1);
        for(int i=2; i<=tot; ++i) {
            ans+=len[1]*(q[i].x-q[i-1].x);
            update(q[i].l,q[i].r-1,q[i].val,1,mm,1);
        }
        printf("Test case #%d\n",++cas);
        printf("Total explored area: %.2f\n\n",ans);
    }
    return 0;
}