1 // File Name: rect1.c  2 // Author: darkdream  3 // Created Time: 2014年02月20日 星期四 20时32分02秒  4 /*  5 ID: dream.y1  6 PROG: rect1  7 LANG: C++  8 */  9 #include<stdio.h> 10 #include<string.h> 11 #include<stdlib.h> 12 #include<time.h> 13 #include<math.h> 14 #define LL long long  15 struct node{ 16     int lx,ly,rx,ry; 17 }a[30000]; 18 int A, B,k; 19 int isin(struct node temp,int  x,int y) 20 { 21     if( x >= temp.lx && x <= temp.rx && y >= temp.ly && y <= temp.ry) 22         return 1;  23     return 0 ;  24 } 25 int t = 0; 26 LL isaren(int i) 27 { 28     if(a[i].lx != -1) 29        return 1ll*(a[i].rx - a[i].lx +1) * (a[i].ry - a[i].ly +1) ; 30     else return 0 ;  31 } 32 void fun0(struct node p ,struct node q) 33 { 34     return ; 35 } 36 void fun1(struct node p,struct node q) 37 { 38     t ++ ;  39     a[t].lx = q.lx ;  40     a[t].ly = p.ry +1;  41     a[t].rx = p.lx -1; 42     a[t].ry = q.ry; 43     if(isaren(t) <= 0) 44         t--; 45 } 46 void fun2(struct node p,struct node q) 47 { 48     t ++ ;  49     a[t].lx = p.lx ;  50     a[t].ly = p.ry +1;  51     a[t].rx = p.rx; 52     a[t].ry = q.ry; 53     if(isaren(t) <= 0) 54         t--; 55  56 } 57 void fun3(struct node p,struct node q) 58 { 59     t ++ ;  60     a[t].lx = p.rx +1 ;  61     a[t].ly = p.ry +1 ;  62     a[t].rx = q.rx; 63     a[t].ry = q.ry; 64     if(isaren(t) <= 0) 65         t--; 66  67 } 68 void fun4(struct node p,struct node q) 69 { 70     t ++ ;  71     a[t].lx = q.lx ;  72     a[t].ly = p.ly;  73     a[t].rx = p.lx-1; 74     a[t].ry = p.ry; 75     if(isaren(t) <= 0) 76         t--; 77 } 78 void fun5(struct node p,struct node q) 79 { 80     t ++ ;  81     a[t].lx = p.rx +1 ;  82     a[t].ly = p.ly;  83     a[t].rx = q.rx; 84     a[t].ry = p.ry; 85     if(isaren(t) <= 0) 86         t--; 87  88 } 89 void fun6(struct node p,struct node q) 90 { 91     t ++ ;  92     a[t].lx = q.lx ;  93     a[t].ly = q.ly;  94     a[t].rx = p.lx - 1; 95     a[t].ry = p.ly - 1; 96     if(isaren(t) <= 0) 97         t--; 98 } 99 void fun7(struct node p,struct node q)100 {101     t ++ ; 102     a[t].lx = p.lx ; 103     a[t].ly = q.ly; 104     a[t].rx = p.rx;105     a[t].ry = p.ly - 1;106     if(isaren(t) <= 0)107         t--;108 109 }110 void fun8(struct node p,struct node q)111 {112     t ++ ; 113     a[t].lx = p.rx + 1 ; 114     a[t].ly = q.ly; 115     a[t].rx = q.rx;116     a[t].ry = p.ly -1;117     if(isaren(t) <= 0)118         t--;119 120 }121 LL ans = 0;122 void figu()123 {124     for(int  i = 1;i <= t;i ++)125     {126         if(isaren(i) >= 1)127         {128         //    printf("%d %d %d %d\n",a[i].lx,a[i].ly,a[i].rx,a[i].ry);129             ans+= isaren(i);130         }131     }132     printf("%I64d\n",ans);133 }134 int lastjudge(node tn1,node tn2)135 {136     if(tn1.lx >= tn2.lx && tn1.lx <= tn2.rx && tn1.rx >= tn2.lx && tn1.rx <= tn2.rx && tn1.ly < tn2.ly && tn1.ry > tn2.ry)137         return 1; 138     if(tn1.ly >= tn2.ly && tn1.ly <= tn2.ry && tn1.ry >= tn2.ly && tn1.ry <= tn2.ry && tn1.lx < tn2.lx && tn1.rx > tn2.rx)139         return 1;140     return 0 ; 141 }142 int next[30004];143 int main(){144     int ca;145     scanf("%d",&ca);146     while(ca--)147     {148         ans = 0 ; 149         t = 0 ; 150         scanf("%d",&k);151         for(int i = 1;i <= 30000;i ++)152             next[i] = i+1;153         for(int i = 1 ;i <= k;i ++)154         {155             t ++ ; 156             scanf("%d %d %d %d",&a[t].lx,&a[t].ly,&a[t].rx,&a[t].ry);157             a[t].rx -- ;158             a[t].ry --;159             int limit = t ;160             int tnext  = 1;  161             for(int j = 1;j < limit ;)162             {163                 //printf("%d\n",j);164                 //printf("%d\n",j);165                 if(j == 0 )166                     break;167                 struct node tn1,tn2;168                 tn1 = a[limit];169                 tn2 = a[j];170                 if(isin(tn2,tn1.lx,tn1.ly) || isin(tn2,tn1.rx,tn1.ry) || isin(tn2,tn1.lx,tn1.ry) || isin(tn2,tn1.rx,tn1.ly)||isin(tn1,tn2.lx,tn2.ly) || isin(tn1,tn2.rx,tn2.ry) || isin(tn1,tn2.lx,tn2.ry) || isin(tn1,tn2.rx,tn2.ly)||lastjudge(tn1,tn2))171                 {172                     a[j].lx = a[j].ly = a[j].rx = a[j].ry = -1; 173                     int hs[10];174                     memset(hs,0,sizeof(hs));175                     if(tn1.lx >= tn2.lx  && tn1.lx <= tn2.rx)176                     {177                         hs[6] = 1; 178                         hs[7] = 1; 179                         hs[8] = 1; 180                     }else tn1.lx = tn2.lx;181 182                     if(tn1.rx >= tn2.lx  && tn1.rx <= tn2.rx)183                     {184                         hs[1] = 1; 185                         hs[2] = 1; 186                         hs[3] = 1; 187                     }else tn1.rx = tn2.rx;188 189                     if(tn1.ly >= tn2.ly  && tn1.ly <= tn2.ry)190                     {191                         hs[1] = 1; 192                         hs[4] = 1; 193                         hs[6] = 1; 194                     }else tn1.ly = tn2.ly;195 196                     if(tn1.ry >= tn2.ly  && tn1.ry <= tn2.ry)197                     {198                         hs[3] = 1; 199                         hs[5] = 1; 200                         hs[8] = 1; 201                     }else tn1.ry = tn2.ry;202                     //     printf("(((((((%d %d %d %d %d\n%d %d %d %d %d))))))\n",tn1.lx,tn1.ly,tn1.rx,tn1.ry,tn1.c,tn2.lx,tn2.ly,tn2.rx,tn2.ry,tn2.c);203                     void (*p[])(node,node) = {fun0,fun1,fun2,fun3,fun4,fun5,fun6,fun7,fun8};204                     for(int s =1 ;s <= 8 ;s ++)205                     {206                         p[s](tn1,tn2);207                     }208                 }209                 if(isaren(j) > 0 && j != 1)210                 {211                    next[tnext] = j ;212                    tnext = j;  213                 }214                 j = next[j];  215             }216         }217         figu();218     }219     return 0 ;220 }