求矩形的面积总和（重合不算）
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=2e6+10; struct line { double l,r,h; int flag; }s[N]; bool cmpline(line a,line b){return a.h<b.h; } double t[N<<2],col[N<<2],b[N]; void up(int pos,int l,int r) { if(col[pos])t[pos]=b[r+1]-b[l]; else if(l==r)t[pos]=0; else t[pos]=t[pos<<1]+t[pos<<1|1]; } void up(int L,int R,int v,int l,int r,int pos) { if(L<=l&&r<=R) { col[pos]+=v; up(pos,l,r);return ; } int m=(l+r)>>1; if(L<=m)up(L,R,v,lson); if(R>m)up(L,R,v,rson); up(pos,l,r); } int main() { int n,num=0; double x1,x2,yy,y2; while(cin>>n,n) { int cnt=0; rep(i,1,n) { scanf("%lf%lf%lf%lf",&x1,&yy,&x2,&y2); b[++cnt]=x1; s[cnt]=(line){x1,x2,yy,1}; b[++cnt]=x2; s[cnt]=(line){x1,x2,y2,-1}; } sort(s+1,s+1+cnt,cmpline); sort(b+1,b+1+cnt); int m=unique(b+1,b+1+cnt)-b-1; double ans=0; rep(i,1,cnt) { int L=lower_bound(b+1,b+1+m,s[i].l)-b; int R=lower_bound(b+1,b+1+m,s[i].r)-b-1;//这里一定要-1 同时 线段树里面右界+1 up(L,R,s[i].flag,1,m,1); ans+=t[1]*(s[i+1].h-s[i].h); } printf("Test case #%d Total explored area: %.2f ",++num,ans); } return 0; }