大致题意： 给你\(N\)个矩形，请你求出它们覆盖的面积（重叠的面积只算一次）。
扫描线
这道题是一道典型的求矩形面积并问题，是扫描线的一个经典运用。这里就不赘述了。
代码
#include<bits/stdc++.h>
#define N 100
using namespace std;
int n,cnt,Exist[N<<4];
double Sum[N<<4],xy[(N<<2)+5];
struct Square
{
int flag,nx,ny1,ny2;
double x,y1,y2;
}a[2*N+5];
map<double,int> p,p_;
map<int,double> f,f_;
//线段树模板--------------------------------------------------------------------
inline void PushUp(int l,int r,int rt)
{
if(Exist[rt]) Sum[rt]=f[r+1]-f[l];
else if(l==r) Sum[rt]=0;
else Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
}
inline void Update(int l,int r,int rt,int L,int R,int v)//线段树的区间修改
{
if(L>R) return;
if(L<=l&&r<=R) {Exist[rt]+=v,PushUp(l,r,rt);return;}
int mid=l+r>>1;
if(L<=mid) Update(l,mid,rt<<1,L,R,v);
if(R>mid) Update(mid+1,r,rt<<1|1,L,R,v);
PushUp(l,r,rt);
}
//----------------------------------------------------------------------------
inline bool cmp(Square x,Square y)
{
return x.nx<y.nx;
}
int main()
{
register int i;int k=0;double x1,x2,y1,y2;
while(~scanf("%d",&n),n)
{
for(cnt=0,p=p_,f=f_,i=1;i<=n;++i)
cin>>x1>>y1>>x2>>y2,a[(i<<1)-1]=(Square){1,0,0,0,xy[(i<<2)-3]=x1,xy[(i<<2)-2]=y1,xy[(i<<2)-1]=y2},a[i<<1]=(Square){-1,0,0,0,xy[i<<2]=x2,y1,y2};
//一个离散化的过程--------------------------------------------------------------------
sort(xy+1,xy+(n<<2)+1);
for(i=1;i<=n<<2;++i)
if(!p[xy[i]]) f[p[xy[i]]=++cnt]=xy[i];
for(i=1;i<=n<<1;++i)
a[i].nx=p[a[i].x],a[i].ny1=p[a[i].y1],a[i].ny2=p[a[i].y2];
//--------------------------------------------------------------------------------
sort(a+1,a+(n<<1)+1,cmp),memset(Exist,0,sizeof(Exist)),memset(Sum,0,sizeof(Sum));
int Now=1;double ans=0.0;//Now表示当前扫描到的边的编号，ans记录面积
for(i=1;i<=cnt;++i)
{
ans+=(f[i]-f[i-1])*Sum[1];//更新ans
if(a[Now].nx^i) continue;//如果当前边不在扫描到的这一列上，就跳过
while(a[Now].nx==i&&Now<=n<<1)
Update(1,cnt,1,a[Now].ny1,a[Now].ny2-1,a[Now].flag),++Now;//修改，操作下一条边
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",++k,ans);
}
return 0;
}
注：线段树用的数组要开大，因为离散化后的边的大小是\(4n\)的（当然，有些打法是\(2n\)的），所以线段树的数组要开\(16n\)。