题目链接：http://poj.org/problem?id=1151
很经典的题目，网上有很多模板代码，自己理解了一天，然后很容易就敲出来了。。。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 110
using namespace std;
int n;
class node
{
public:
int l,r;//端点坐标的映射值(整数值)
double cnt;
double c;
double lf,rf;//实际的端点坐标
};
node segTree[maxn*];
class Line
{
public:
double x;
double y1;
double y2;
double f;//f=1表示左边，f=-1表示矩形的右边
};
Line line[maxn];
double y[maxn];
bool cmp(Line a, Line b)
{
return a.x < b.x;
}
void Build(int num, int l, int r)
{
segTree[num].l=l;
segTree[num].r=r;
segTree[num].cnt=segTree[num].c=;
segTree[num].lf=y[l];
segTree[num].rf=y[r];
if(l+==r) return ;
int mid=(l+r)/;
Build(num*,l,mid);
Build(num*+,mid,r);
}
void calen(int num)//计算边的有效长度
{
if(segTree[num].c > ) //表示当前边为直接有效部分 cnt存边的长度
{
segTree[num].cnt=segTree[num].rf-segTree[num].lf;
return ;
}
else//如果当前边不是直接有效部分 可以理解为当前边已经不存在
{
if(segTree[num].l+ ==segTree[num].r) //如果当前边为最小的单元(就是没有孩子了),那么其间接有效长度为0
{
segTree[num].cnt=;
}
else//否则其有效长度为孩子的有效长度和
{
segTree[num].cnt=segTree[num*].cnt+segTree[num*+].cnt;
return ;
} }
}
void Update(int num,Line e)
{
if(segTree[num].lf== e.y1 && segTree[num].rf ==e.y2)
{
segTree[num].c+=e.f;
calen(num);
return ;
}
if(segTree[num*].rf>=e.y2) Update(num*,e);
else
if(segTree[num*+].lf<=e.y1) Update(num*+,e);
else
{
Line tmp=e;
tmp.y2=segTree[num*].rf;
Update(num*,tmp);
tmp=e;
tmp.y1=segTree[num*+].lf;
Update(num*+,tmp);
}
calen(num);
}
int main()
{
int iCase=;
double x1,x2,y1,y2;
while(scanf("%d",&n)!=EOF && n)
{
int t=;
for(int i=;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[t].x=x1;
line[t].y1=y1;
line[t].y2=y2;
line[t].f=;
y[t]=y1;
t++;
line[t].x=x2;
line[t].y1=y1;
line[t].y2=y2;
line[t].f=-;
y[t]=y2;
t++;
}
sort(y+,y+t);
sort(line+,line+t,cmp);
Build(,,t-);
Update(,line[]);
double ans=;
for(int i=;i<t;i++)
{
ans+=segTree[].cnt*(line[i].x- line[i-].x);
Update(,line[i]);
//segTree[1].cnt是位于坐标line[i-1].x的最终的有效边长
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",iCase++,ans); } return ;
}