线段树扫描线经典题：求矩形面积并
思想：对y轴坐标离散化 分别计算各个小矩形的面积
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=513;
struct Rect{
double x1,y1,x2,y2;
};
struct Sline{
double y1,y2,x;
int Y1,Y2;
int flag;
Sline(){};
Sline(Rect r,int side){
y1=r.y1;y2=r.y2;
if(side==0) x=r.x1,flag=1;
else x=r.x2,flag=-1;
}
bool operator<(const Sline &b) const{
return x<b.x;
}
};
int n;
Rect r[111];
Sline s[222];
double tmp[222];
int cnt,tcnt;
struct SegTree{
int c[N<<1],Q;
double len[N<<1];
double slen[N<<1];
void Init(int n){
for(Q=1;Q<=n+2;Q<<=1) ;
memset(slen,0,sizeof(slen));
memset(len,0,sizeof(len));
memset(c,0,sizeof(c));
}
void Uslen(int p,double l){
p+=Q;
while(p) slen[p]+=l,p>>=1;
}
void pushup(int rt){
if(c[rt]>0) len[rt]=slen[rt];
else{
if(rt>=Q) len[rt]=0;
else len[rt]=len[rt<<1]+len[rt<<1|1];
}
}
void update(int L,int R,int l,int r,int rt,int x){
if(L<=l && r<=R){
c[rt]+=x;
pushup(rt);
}
if(rt>=Q) return ;
int m=(l+r)>>1;
if(L<=m) update(L,R,l,m,rt<<1,x);
if(m<R) update(L,R,m+1,r,rt<<1|1,x);
pushup(rt);
}
void update(int L,int R,int x){
update(L,R,0,Q-1,1,x);
}
}st;
int toSline(Rect r[],Sline s[],double tmp[],int n){
cnt=0,tcnt=0;
for(int i=0;i<n;i++){
s[cnt++]=Sline(r[i],0);
s[cnt++]=Sline(r[i],1);
tmp[tcnt++]=r[i].y1;
tmp[tcnt++]=r[i].y2;
}
sort(tmp,tmp+tcnt);
tcnt=unique(tmp,tmp+tcnt)-tmp;
for(int i=0;i<cnt;i++){
s[i].Y1=lower_bound(tmp,tmp+tcnt,s[i].y1)-tmp+1;
s[i].Y2=lower_bound(tmp,tmp+tcnt,s[i].y2)-tmp;
}
sort(s,s+cnt);
st.Init(tcnt);
for(int i=1;i<tcnt;i++){
st.Uslen(i,tmp[i]-tmp[i-1]);
}
return cnt;
}
int main() {
int casno=1;
while(scanf("%d",&n)&&n){
for(int i=0;i<n;i++) scanf("%lf %lf %lf %lf",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2);
toSline(r,s,tmp,n);
st.update(s[0].Y1,s[0].Y2,s[0].flag);
double ans=0.0;
for(int i=1;i<cnt;i++){
ans+=st.len[1]*(s[i].x-s[i-1].x);
st.update(s[i].Y1,s[i].Y2,s[i].flag);
}
printf("Test case #%d\n",casno++);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}