求矩阵的并，也就是要求所有的面积。那可以吧总的图形按照矩阵来切割。使其为一块一块。
输入的时候用坐标表示，这里扫描线从下到上扫描。初始时让下面的边为1，上面的为-1；
用一条先从下面开始想上扫描。遇到更新线段树，加入该条边，为-1时就除去改变。
这样从下到上一遍扫描就可以得到线段的长度。从下到上的过程中，一旦遇到一条边，那就计算他的高度。
高度*长度就是面积。
/* 那叶子节点[l,l]的长度不就变成0，显然这是有问题的 线段树的每一个节点表示一段区间，[l,r]该区间表示LX[r+1]-LX[l]的长度 1___2___3___4___5离散后的状况 1 2 3 4 线段树中的每一个节点 */ #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 1005 double x[maxn<<2]; struct seg { double l,r,h; int f; }s[maxn<<1]; struct node { int cnt;//cnt表示该区间是否被完全覆盖 如果cnt==1表示被完全覆盖一次 //cnt=0表示为被完全覆盖 但是不代表未覆盖，cnt>1表示被多次完全覆盖 double len; }tree[maxn*8]; bool cmp(seg a,seg b) { return a.h<b.h; } int find(double val,int l,int r) { int left=l,right=r; int mid; while(left<=right) { mid=(left+right)/2; if(x[mid]==val) return mid; else if(x[mid]>val) right=mid-1; else left=mid+1; } return -1; } void build(int l,int r,int rt) { if(l==r) { tree[rt].cnt=0; tree[rt].len=0; return ; } int m=(l+r)/2; build(lson); build(rson); } void getlen(int rt,int l,int r) { if(tree[rt].cnt)//如果整一段被覆盖，直接求得长度 { tree[rt].len=x[r+1]-x[l]; } else if(l==r)//叶子节点 tree[rt].len=0; else //不是叶子但也未整段覆盖，从儿子节点获得 tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len; } void updata(int L,int R,int c,int l,int r,int rt) { if(l>=L&&R>=r) { tree[rt].cnt+=c; getlen(rt,l,r); return ; } int m=(l+r)/2; if(m>=L) updata(L,R,c,lson); if(R>m) updata(L,R,c,rson); getlen(rt,l,r); } int main() { int n,m,t,i,j,ff=0; double x1,x2,y1,y2; while(scanf("%d",&n)!=EOF) { if(!n) break; m=0; for(i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); s[m].l=x1;s[m].r=x2;s[m].h=y1;s[m].f=1; //下边界 s[m+1].l=x1;s[m+1].r=x2;s[m+1].h=y2;s[m+1].f=-1; //上边界 x[m]=x1; x[m+1]=x2; m=m+2; } sort(s,s+m,cmp); sort(x,x+m); int k=1; for(i=1;i<m;i++)//去重复 { if(x[i]!=x[i-1]) x[k++]=x[i]; } build(0,k-1,1); double ans=0; for(i=0;i<m;i++) { int ll=find(s[i].l,0,k-1);//二分找位置 int rr=find(s[i].r,0,k-1)-1;//因为这里表示的为线段 不是点。 updata(ll,rr,s[i].f,0,k-1,1); ans+=(s[i+1].h-s[i].h)*tree[1].len; } printf("Test case #%d ",++ff); printf("Total explored area: %.2lf ",ans); } }