题意:给你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 #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 }
2)还可以用线段树来求解这题
hnu12884 Area Coverage 矩形分割 or 线段树,布布扣,bubuko.com
hnu12884 Area Coverage 矩形分割 or 线段树
原文:http://www.cnblogs.com/zyue/p/3906468.html