離散化+掃描線+線段樹。 雖然這題直接離散化也能過，但想要學習一下線段樹求矩形並，就網搜各種線段樹求矩形並的方法。其實做法還是跟離散化的做法差不多。
先介紹離散化+掃描線的做法(這種情況適應矩形數目不是很多的時候）：
1，將矩形的四條邊無限延長，則將平面區域分為了多個小矩形區域。我們要求的區域面積就是其中一些的小矩形的面積的和。（這一步只是理解，無實際操作）
2，分別將上述水平的劃分線和豎直的劃分線按從小到大排序。
3，對於輸入的每個矩形，枚舉每個x軸斷點，再枚舉每個y軸斷點，判斷每個小矩形是否在當前矩形中，是的話就記錄record[i][j]=1否則為0; 然後用record[i][j[乘以小矩形的面積並累加；
下面介紹線段樹的做法：
1,2步同上；
3，我們所說的線段樹是對x軸建樹。我們的理解中用y軸的平行線劃分矩形。然後對於每個輸入的矩形我們把它的上下兩條邊記錄下來（包括這條邊兩個端點的x軸坐標，高度，上邊或者下邊等信息）。依次從高度小的邊開始，把這條邊對應的x軸區域在線段樹中覆蓋。當然這裡矩形的下邊是覆蓋，上邊是刪除。 每插入一條邊後由於pushup的作用，sum【1】記錄了當前邊插入後整個x軸被覆蓋的長度。然後用這條邊所在的直線與緊鄰它的上一條水平直線間的距離乘以sum【1】就是被夾在這兩條水平線間的面積。不斷累加就可以了；
思路大概是這樣，但還有一些細節問題需要注意。詳見代碼。
[cpp]
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#define maxn 1000
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
typedef struct
{
double l,r,h; int s; // s用來記錄這條邊是上邊還是下邊
}Seg;
Seg ss[maxn];
int cnt[4*maxn]; double sum[4*maxn]; // cnt用來記錄線段樹中節點所對應的區間被覆蓋的次數，sum記錄覆蓋的區間長度
double X[maxn];
int Cmp( Seg aa, Seg bb)
{
return aa.h < bb.h;
}
int Bin( double key ,int n)
{
int l=1,r=n,m; double eps=1e-7;
while( l <= r )
{
m=(l+r)/2;
if( fabs(X[m]-key) < eps ) return m;
if( X[m] < key ) l=m+1;
else r=m-1;
}
return -1;
}
void update(int a,int b,int c,int l,int r,int rt)
{
if( l==a && r==b )
{
cnt[rt]+=c;
if( cnt[rt] ) sum[rt]=X[r+1]-X[l];
else if (l == r) sum[rt] = 0;
else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
return ;
}
int m=(l+r)/2;
if( b<=m ) update(a,b,c,l,m,rt<<1);
else if( a>m ) update(a,b,c,m+1,r,rt<<1|1);
else
{
update(a,m,c,l,m,rt<<1);
update(m+1,b,c,m+1,r,rt<<1|1);
}
if( cnt[rt] ) sum[rt]=X[r+1]-X[l];
else if (l == r) sum[rt] = 0;
else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int main()
{
int i,j,n,k,len,cas=1; double a,b,c,d;
while( scanf("%d",&n) , n )
{
k=1;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
X[k]=a; ss[k].l=a; ss[k].r=c ; ss[k].h=b; ss[k].s=1;
k++;
X[k]=c; ss[k].l=a; ss[k].r=c ; ss[k].h=d; ss[k].s=-1;
k++;
}
sort(X+1,X+k);
sort(ss+1,ss+k,Cmp);
len=2;
for(i=2;i<k;i++) // x軸去重
if( X[i]!=X[i-1] ) X[len++]=X[i];
double ret=0.0;
memset(sum,0,sizeof(sum)); memset( cnt,0,sizeof(cnt));
for(i=1;i<k;i++)
{
int l = Bin( ss[i].l , len-1 );
int r = Bin( ss[i].r , len-1)-1 ; // 這裡要注意-1
if( l<=r ) update( l,r,ss[i].s,1,len-2,1); //這裡線段樹中的節點不是對應線段的斷點，而是對應此端點到後面一個端點的線段，所以上面求出的r要減1
ret+= sum[1]*(ss[i+1].h-ss[i].h);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++,ret);
}
return 0;
}
