1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 100010  5 using namespace std;  6   7 int t,n;  8 double Y[maxn],X[maxn];  9 struct point 10 { 11     double x; 12     double y_up; 13     double y_down; 14     int lr; 15     bool operator <(const point &a) const 16     { 17         return x<a.x; 18     } 19 }p[maxn*4]; 20  21 struct node 22 { 23     double x; 24     double y_up; 25     double y_down; 26     int cover; 27     bool flag; 28 }tree[maxn*4]; 29  30 void build(int i,int l,int r) 31 { 32     tree[i].x=-1; 33     tree[i].y_up=Y[r]; 34     tree[i].y_down=Y[l]; 35     tree[i].cover=0; 36     tree[i].flag=true; 37     if(l+1==r) 38     { 39         tree[i].flag=false; 40         return ; 41     } 42     int mid=(l+r)>>1; 43     build(i<<1,l,mid); 44     build(i<<1|1,mid,r); 45 } 46  47 double update(int i,double l,double r,double x,int lr) 48 { 49     if(tree[i].y_down>=r||tree[i].y_up<=l) return 0; 50     if(!tree[i].flag) 51     { 52         if(tree[i].cover>1) 53         { 54             tree[i].cover+=lr; 55             double sum=(x-tree[i].x)*(tree[i].y_up-tree[i].y_down); 56             tree[i].x=x; 57             return sum; 58         } 59         else 60         { 61             tree[i].cover+=lr; 62             tree[i].x=x; 63             return 0; 64         } 65     } 66     else return update(i<<1,l,r,x,lr)+update(i<<1|1,l,r,x,lr); 67 } 68 int main() 69 { 70     scanf("%d",&t); 71     while(t--) 72     { 73         scanf("%d",&n); 74         int cnt=0; 75         for(int i=1; i<=n; i++) 76         { 77             double x1,y1,x2,y2; 78             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 79             p[cnt].x=x1; 80             p[cnt].y_down=y1; 81             p[cnt].y_up=y2; 82             p[cnt].lr=1; 83             X[cnt]=x1; 84             Y[cnt++]=y1; 85             p[cnt].x=x2; 86             p[cnt].y_down=y1; 87             p[cnt].y_up=y2; 88             X[cnt]=x2; 89             p[cnt].lr=-1; 90             Y[cnt++]=y2; 91         } 92         sort(Y,Y+cnt); 93         sort(X,X+cnt); 94         sort(p,p+cnt); 95         build(1,0,cnt-1); 96         double ans=0; 97         for(int i=0; i<cnt; i++) 98         { 99             ans+=update(1,p[i].y_down,p[i].y_up,p[i].x,p[i].lr);100         }101         printf("%.2lf\n",ans);102     }103     return 0;104 }