题意：给你n个二维平面上的矩形，可以两两覆盖，问最后覆盖的总面积为多少
解题思路：1）矩形状分割，可以知道，每多出一个矩形就和前面所有产生的矩形判断，看是有相交，如果有的话，就对前面的矩形进行分割，最多可以分割成8块，因为这个算法是n×n的算法时间复杂度，所以我们还需要在枚举的时候加速，采用引导值（下一个不为0的矩阵的值），最后6700ms过了
解题代码：
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 #include10 #include 11 #include 12 #include 13 #include 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 }
2)还可以用线段树来求解这题