原題：http://poj.org/problem?id=1151
題意：給出若干組矩形左上角和右下角的坐標(biāo)（坐標(biāo)可能為小數(shù)）磁滚，求出所有矩形所覆蓋的面積拣挪，重疊部分只算一次擦酌。
思路：如圖所示，假想一條掃描線從下向上移動菠劝，每次遇到矩形上底或者下底便計算一次掃過的矩形面積赊舶，并加到總和中去。如圖所示，依次求出不同顏色矩形的面積笼平，想加便可求得所有矩形覆蓋的總面積园骆。
掃描線的移動由程序來實現(xiàn)實質(zhì)上是在各個矩形的底邊按縱坐標(biāo)從小到大跳動，每跳動一次需要計算一次掃過的矩形面積寓调。面積=跳動的長度*該段x方向被矩形覆蓋的長度锌唾，暫且將其設(shè)成S=Y*X。
首先夺英，我們需要將矩形的底邊的縱坐標(biāo)按從小到大進(jìn)行排序晌涕，Y即為相鄰兩個底邊的差值，同時痛悯，我們還需要記錄底邊的橫坐標(biāo)范圍余黎，以便每掃過一條底邊后更新X（當(dāng)掃面線經(jīng)過一條底邊時，意味著有一個矩形進(jìn)入或者退出掃描區(qū)域）载萌。于是惧财，我們定義以下結(jié)構(gòu)體：
struct line{
double lf,rf,y; //某底邊的左右端點坐標(biāo)，縱坐標(biāo)
int d; //區(qū)分上底和下底的標(biāo)記炒考，為方便更新X可缚，下底設(shè)為1，上底設(shè)為-1
}scan[MAXN];
如何高效地更新X呢斋枢，考慮到X實質(zhì)上是掃描線上矩形所覆蓋的總長度帘靡，遇到底邊是相當(dāng)于修改掃描線上某一區(qū)間被覆蓋的情況。類似于區(qū)間修改與求和問題瓤帚，由此聯(lián)想到線段樹描姚，因此可以使用線段樹來維護掃描線上被矩形覆蓋的情況。但是橫坐標(biāo)為浮點數(shù)戈次，因此首先要將所有的橫坐標(biāo)進(jìn)行排序離散化處理轩勘，即將所有的矩形的邊橫坐標(biāo)從小到大排序，將排序序號作為線段樹的區(qū)間號怯邪。同時绊寻，我們還要保存原來真實的浮點值，以便計算長度悬秉。
因此樹節(jié)點可以如下定義：
struct node{
int l,r;//左右整點區(qū)間
int c;//覆蓋標(biāo)記
double cnt;//覆蓋長度
double lf,rf;//左右實數(shù)區(qū)間
}tree[MAXN*4];
覆蓋標(biāo)記用來表示該節(jié)點所代表的區(qū)間被一個完整的矩形完全覆蓋（注意是被一個矩形完全覆蓋澄步，而非由多個矩形完全覆蓋），覆蓋長度表示該節(jié)點所代表的區(qū)間被所有矩形所覆蓋的長度和泌。
//ac代碼
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 201
struct node{
int l,r;//左右整點區(qū)間
int c;//覆蓋標(biāo)記
double cnt;//覆蓋長度
double lf,rf;//左右實數(shù)區(qū)間
}tree[MAXN*4];
struct line{
double lf,y,rf;
int d;
}scan[MAXN];
double x[MAXN];
bool cmp(line l1,line l2){
return l1.y<l2.y;
}
void build(int i,int s,int e){
tree[i].l=s;
tree[i].r=e;
tree[i].lf=x[s];
tree[i].rf=x[e];
tree[i].c=tree[i].cnt=0;
if (s+1==e) return;
int mid = (s+e)>>1;
build(i<<1,s,mid);
build(i<<1|1,mid,e);
}
void calen(int i){
if (tree[i].c>0){
tree[i].cnt=tree[i].rf-tree[i].lf; //cout<<i<<" "<<tree[i].lf<<" "<<tree[i].rf<<" "<<tree[i].cnt<<"#"<<endl;
return;
}
if (tree[i].r-tree[i].l==1) tree[i].cnt=0;
else tree[i].cnt=tree[i<<1].cnt+tree[i<<1|1].cnt;
}
void updata(int i,line l){
if (tree[i].lf>=l.lf&&tree[i].rf<=l.rf){
tree[i].c+=l.d;
calen(i);
return;
}
if (tree[i].lf>=l.rf||tree[i].rf<=l.lf) return;
updata(i<<1,l);
updata(i<<1|1,l);
calen(i);
}
int main()
{
int n,i,j,icase=0;
double x1,y1,x2,y2;
while(~scanf("%d",&n)){
if (n==0) break;
icase++;
for (i=0;i<n;++i){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
scan[2*i].lf=x1;
scan[2*i].rf=x2;
scan[2*i].y=y1;
scan[2*i].d=1;
scan[2*i+1].lf=x1;
scan[2*i+1].rf=x2;
scan[2*i+1].y=y2;
scan[2*i+1].d=-1;
x[2*i]=x1;
x[2*i+1]=x2;
}
sort(x,x+2*n);
sort(scan,scan+2*n,cmp);
//for (i=0;i<2*n;++i) cout<<x[i]<<" "<<scan[i].y<<" ";
//cout<<endl;
build(1,0,2*n-1);
updata(1,scan[0]);
double res=0;
//cout<<scan[0].lf<<" "<<scan[0].rf<<endl;
//for (i=1;i<=7;++i) cout<<tree[i].c<<" "<<tree[i].cnt<<" "<<tree[i].lf<<" "<<tree[i].rf<<endl;
//cout<<"$"<<endl;
for (i=1;i<2*n;++i){
res+=(scan[i].y-scan[i-1].y)*tree[1].cnt;
updata(1,scan[i]);
//cout<<scan[i].lf<<" "<<scan[i].rf<<endl;
//for (int k=1;k<=7;++k) cout<<tree[k].c<<" "<<tree[k].cnt<<endl;
//cout<<"$"<<endl;
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",icase,res);
}
}
