/* 不是叶子节点 ，且cnt=1.注意这里，cnt=1确切的意义是什么， 应该是，可以确定，这个区间被完全覆盖了1次， 而有没有被完全覆盖两次或以上则不知道无法确定，那么怎么怎么办了， 只要加上t[lch].s + t[rch].s 即，看看左右孩子区间被覆盖了一次或以上的长度， 那么叠加在双亲上就是双亲被覆盖两次或以上的长度 */ #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 1005 struct segment { double l,r,h; int f; }s[maxn*2]; struct node { int cnt; double len1;//记录一次及以上的 double len2;//记录二次及以上的 }tree[maxn*8]; double mark[maxn<<1]; bool cmp(segment a,segment b) { return a.h<b.h; } void build(int l,int r,int rt) { tree[rt].cnt=0; tree[rt].len1=tree[rt].len2=0; if(l==r) { return ; } int m=(l+r)/2; build(lson); build(rson); } /* 重点。 若该节点的cnt >= 2,说明被至少两条线段覆盖，那么len1=len2=区间长度。 若该节点的cnt == 1，说明该区间被一条线段覆盖，len1=区间长度，只要左右节点的len1有值， 那么那些长度一定是至少被覆盖两次的，因此len2为左右节点的len1之和。 若该节点的cnt = 0，说明没被完全覆盖，直接用其左右节点更新。 还要注意特判叶子节点。 */ void getlen(int l,int r,int rt) { if(tree[rt].cnt>=2)//>=2时很好理解，就是覆盖2次或以上，直接减一减 { tree[rt].len1=mark[r+1]-mark[l]; tree[rt].len2=mark[r+1]-mark[l]; } else if(tree[rt].cnt==1)//此处需要注意 //由于cnt大于0,所以覆盖一次或以上的部分直接得到，而由于完全覆盖一次 //可能其他部分有覆盖，此时就可以根据左右孩子来，由于len1记录覆盖一次或 //以上的，因为已经完全覆盖了一次，只要加上左右孩子的一次或以上覆盖的值 //那么就是2次或以上覆盖的值。 { tree[rt].len1=mark[r+1]-mark[l];//因为覆盖一次，len1还要继续加 if(l == r)//由于覆盖一次，又只有一个l==r，所以len2为0 { tree[rt].len2=0; } else { tree[rt].len2=tree[rt<<1].len1+tree[rt<<1|1].len1; } } else if(tree[rt].cnt==0)//为完全覆盖，根据孩子来。此处与上面等于1出相似，可以发现，如果为完全覆盖 //就可以根据左右孩子得到覆盖的，那cnt等于1时，要求覆盖2次的时候就也可以 //根据孩子来。 { if(l == r) tree[rt].len1=tree[rt].len2=0; else { tree[rt].len1=tree[rt<<1].len1+tree[rt<<1|1].len1; tree[rt].len2=tree[rt<<1].len2+tree[rt<<1|1].len2; } } } void updata(int L,int R,int c,int l,int r,int rt) { if(l>=L&&R>=r) { tree[rt].cnt+=c; getlen(l,r,rt); return ; } int m=(l+r)/2; if(m>=L) updata(L,R,c,lson); if(R>m) updata(L,R,c,rson); getlen(l,r,rt); } int find(double val,int x,int y) { int l=x,r=y,m; while(l<=r) { m=(l+r)/2; if(mark[m]==val) return m; else if(mark[m]>val) r=m-1; else l=m+1; } return -1; } int main() { int t,n,i; double x1,x2,y1,y2; scanf("%d",&t); while(t--) { scanf("%d",&n); int 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;mark[m++]=x1; s[m].l=x1;s[m].r=x2;s[m].h=y2;s[m].f=-1;mark[m++]=x2; } sort(s,s+m,cmp); sort(mark,mark+m); int k=1; for(i=1;i<m;i++) { if(mark[i]!=mark[i-1]) mark[k++]=mark[i]; } /* for(i=0;i<k;i++) printf("%.2lf ",mark[i]); printf(" "); */ 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].len2; } printf("%.2lf ",ans); } }