链接：http://acm.hdu.edu.cn/showproblem.php?pid=1542
题意：
求所给矩形的覆盖面积
题解：
利用扫描线的思想，先将坐标离散化，之后以y轴分成多个矩形求解，可以让下边界+1上边界-1
问题就转化为了：求区间中有多少个非0数，要求支持区间+1 -1操作
我们可以通过维护区间最小值以及最小值的个数来完成这件事情
代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include <iostream>
#define maxn 5000
#define INF 59999999
#define eps 1e-6
#define mid (h+t)/2
using namespace std;
struct re
{
double a;int b;
}a[maxn],b[maxn];
struct ree
{
int h,t,x,lazy;
double sum,tot;
}p[maxn*4];
double c[maxn];
int a1[maxn];
bool cmp(re x,re y)
{
if (x.a<y.a) return(true); else return(false);
}
void build(int x,int h,int t)
{
p[x].h=h; p[x].t=t; p[x].x=0;
if (h==t)
{
p[x].sum=p[x].tot=c[h+1]-c[h];
return;
}
build(x*2,h,mid);
build(x*2+1,mid+1,t);
p[x].sum=p[x].tot=p[x*2].sum+p[x*2+1].sum;
}
void updata(int x)
{
p[x].x=min(p[x*2].x,p[x*2+1].x);
if (p[x*2].x==p[x*2+1].x)
{
p[x].sum=p[x*2].sum+p[x*2+1].sum;
}
else
{
if (p[x*2].x<p[x*2+1].x) p[x].sum=p[x*2].sum;
else p[x].sum=p[x*2+1].sum;
}
return;
}
void down(int x)
{
if (p[x].lazy==0) return;
p[x].x+=p[x].lazy;
p[x*2].lazy+=p[x].lazy;
p[x*2+1].lazy+=p[x].lazy;
p[x].lazy=0;
}
void insert(int x,int h,int t,int sum)
{
down(x);
if (p[x].h>t|| p[x].t<h) return;
if (h<=p[x].h &&p[x].t<=t)
{
p[x].lazy+=sum; down(x); return;
}
insert(x*2,h,t,sum); insert(x*2+1,h,t,sum);
updata(x);
}
double query(int x,int h,int t)
{
down(x);
if (p[x].h>t||p[x].t<h) return(0);
if (h<=p[x].t && p[x].t<=t)
{
if (p[x].x==0) return(p[x].tot-p[x].sum); else return(p[x].tot);
}
return(query(x*2,h,t)+query(x*2+1,h,t));
}
int main()
{int n,o=0;
while (cin>>n&&n!=0)
{
o++;
memset(p,0,sizeof(p));
for (int i=1;i<=2*n;i++) a[i].b=i,b[i].b=i;
for (int i=1;i<=n;i++)
{
cin>>a[2*i-1].a>>b[2*i-1].a>>a[2*i].a>>b[2*i].a;
}
sort(a+1,a+1+2*n,cmp);
sort(b+1,b+1+2*n,cmp);
int ll=0; a[0].a=INF;
for (int i=1;i<=2*n;i++)
{
if (abs(a[i].a-a[i-1].a)>eps) ll++;
a1[a[i].b]=ll;
c[ll]=a[i].a;
}
double ans=0;
build(1,1,ll-1);
for (int i=1;i<2*n;i++)
{
int pp,tmp=b[i].b;
if (tmp%2==1) pp=1 ;else pp=-1;
insert(1,a1[(tmp+1)/2*2-1],a1[(tmp+1)/2*2]-1,pp);
ans+=(b[i+1].a-b[i].a)*query(1,1,ll-1);
}
cout<<"Test case #"<<o<<endl<<"Total explored area: " ;
printf("%.2f
",ans);
}
}