题意：给出矩形两对角点坐标，求矩形面积并。
解法：线段树+离散化。
每加入一个矩形，将两个y值加入yy数组以待离散化，将左边界cover值置为1，右边界置为2，离散后建立的线段树其实是以y值建的树，线段树维护两个值:cover和len,cover表示该线段区间目前被覆盖的线段数目，len表示当前已覆盖的线段长度（化为离散前的真值），每次加入一条线段，将其y_low,y_high之间的区间染上line[i].cover，再以tree[1].len乘以接下来的线段的x坐标减去当前x坐标，即计算了一部分面积。
如图情况，将会计算三次面积：
代码：
#include <iostream>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define eps 1e-8
using namespace std;
#define N 307 struct node
{
int cov;
double len;
}tree[*N]; struct Line
{
double y1,y2,x;
int cov;
}line[*N];
double yy[*N]; int cmp(Line ka,Line kb)
{
return ka.x < kb.x;
} int bsearch(int l,int r,double x)
{
while(l <= r)
{
int mid = (l+r)/;
if(fabs(yy[mid]-x) < eps)
return mid;
if(x > yy[mid])
l = mid+;
else
r = mid-;
}
return l;
} void build(int l,int r,int rt)
{
tree[rt].cov = ;
tree[rt].len = ;
if(l == r-) return;
int mid = (l+r)/;
build(l,mid,*rt);
build(mid,r,*rt+);
} void pushup(int l,int r,int rt)
{
if(tree[rt].cov)
tree[rt].len = yy[r]-yy[l];
else if(l+ == r)
tree[rt].len = ;
else
tree[rt].len = tree[*rt].len + tree[*rt+].len;
} void update(int l,int r,int aa,int bb,int cover,int rt)
{
if(aa <= l && bb >= r)
{
tree[rt].cov += cover;
pushup(l,r,rt);
return;
}
if(l+ == r) return;
int mid = (l+r)/;
if(aa <= mid)
update(l,mid,aa,bb,cover,*rt);
if(bb > mid)
update(mid,r,aa,bb,cover,*rt+);
pushup(l,r,rt);
} int main()
{
int n,m,cs = ,i,j;
double x1,y1,x2,y2;
while(scanf("%d",&n)!=EOF && n)
{
m = ;
for(i=;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[m].x = x1,line[m].y1 = y1,line[m].y2 = y2,line[m].cov = ,yy[m++] = y1;
line[m].x = x2,line[m].y1 = y1,line[m].y2 = y2,line[m].cov = -,yy[m++] = y2;
}
m--;
sort(yy+,yy+m+);
int cnt = ;
for(i=;i<=m;i++)
{
if(yy[i] != yy[i-])
yy[cnt++] = yy[i];
}
cnt--;
build(,cnt,);
sort(line+,line+m+,cmp);
double ans = 0.0;
printf("Test case #%d\n",cs++);
for(i=;i<m;i++)
{
int L = bsearch(,cnt,line[i].y1);
int R = bsearch(,cnt,line[i].y2);
update(,cnt,L,R,line[i].cov,);
ans += tree[].len*(line[i+].x-line[i].x);
}
printf("Total explored area: %0.2lf\n\n",ans);
}
return ;
}