http://acm.hdu.edu.cn/showproblem.php?pid=1255
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 ",ans); 102 } 103 return 0; 104 }