也是很久之前的题目，一直没做
做完之后觉得基本的离散化和扫描线还是不难的，由于本题要离散x点的坐标，最后要计算被覆盖的x轴上的长度，所以不能用普通的建树法，建树建到r-l==1的时候就停止，表示某段而不是某点，同样，左子树和右子树要变成 L MID ， MID R
比如1-4子树就是 1-2,2-4。。。2-4再分成2-3,3-4.
然后就是经典的扫描线用法，对下边设标记为1，上边设标记为-1，每次求得x轴被覆盖的长度，乘以和下一条线段的距离（即矩形的高）即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid,r
using namespace std;
const int N = 210;
double d[N*N];
int flag[N*N];
int n;
double X[N];
struct node
{
double l,r,y,f;
bool operator < (const node &rhs) const{
return y<rhs.y;
}
}seg[N];
void build(int rt,int l,int r)
{
flag[rt]=0;
d[rt]=0;
if (r-l<=1){
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
}
void up(int rt,int l,int r)
{
if (flag[rt]>0){
d[rt]=X[r]-X[l];
}
else
{
if (r-l==1) d[rt]=0;
else d[rt]=d[rt<<1]+d[rt<<1|1];
}
}
void cover(int L,int R,double v,int rt,int l,int r)
{
//cout<<l<<" @@@ "<<r<<endl;
if (L<=l && r<=R){
flag[rt]+=v;
up(rt,l,r);
return;
}
if (r-l<=1) return;
int mid=(l+r)>>1;
if (R<=mid) cover(L,R,v,lson);
else
if (L>mid) cover(L,R,v,rson);
else
{
cover(L,R,v,lson);
cover(L,R,v,rson);
}
up(rt,l,r);
}
int main()
{
double xa,ya,xb,yb;
int kase=0;
while (scanf("%d",&n)!=EOF)
{
if (n==0) break;
int cnt=1;
for (int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);
X[cnt]=xa;
seg[cnt++]=(node){xa,xb,ya,1.0};
X[cnt]=xb;
seg[cnt++]=(node){xa,xb,yb,-1.0};
}
sort(X+1,X+cnt);
sort(seg+1,seg+cnt);
int tmp=1;
for (int i=2;i<cnt;i++){
if(X[i]!=X[i-1]){
X[++tmp]=X[i];
}
}
build(1,1,tmp);
double ans=0;
for (int i=1;i<cnt-1;i++){
//cout<<seg[i].l<<" .. "<<seg[i].r<<endl;
int l1=lower_bound(X+1,X+1+tmp,seg[i].l)-X;
int l2=lower_bound(X+1,X+1+tmp,seg[i].r)-X;
//cout<<l1<<" "<<l2<<" "<<X[l1]<<" "<<X[l2]<<endl;
cover(l1,l2,seg[i].f,1,1,tmp);
//cout<<d[1]<<endl;
ans+=d[1]*(seg[i+1].y-seg[i].y);
//cout<<ans<<endl;
}
printf("Test case #%d
",++kase);
printf("Total explored area: %.2lf
",ans);
puts("");
}
return 0;
}