HDU 1542 传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1542
题目大意就是几个矩形相交，然后求出总的覆盖面积，覆盖多次的按一次算。典型的面积并问题。
大体思路：
记录所给的点，排序，去掉重复的点，对点编号，可以理解成存放点的数组的下表即为编号。
对Y轴建立线段树，利用线段树计算面积。
AC_code：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <cstdlib> 6 7 using namespace std; 8 9 double x[2200],y[2200]; 10 11 double st[2200][8000]; 12 13 struct N1 14 { 15 double x1,x2,y1,y2; 16 }a[1100]; 17 18 int del(double *t,int n)// 去掉重复点的函数 19 { 20 double s[2200]; 21 int top = 0,i; 22 for(i = 0;i < n; i++) 23 { 24 if(top == 0) 25 { 26 s[top++] = t[i]; 27 } 28 else if(t[i] != s[top-1]) 29 { 30 s[top++] = t[i]; 31 } 32 } 33 for(i = 0;i < top; i++) 34 { 35 t[i] = s[i]; 36 } 37 return top; 38 } 39 40 int check_site(double *t,int s,int e,double x)//二分查找当前点的对应编号 41 { 42 if(s == e) 43 return s; 44 int m = (s+e)/2; 45 if(x == t[m]) 46 return m; 47 if(x < t[m]) 48 return check_site(t,s,m-1,x); 49 else return check_site(t,m+1,e,x); 50 } 51 52 double change(double *st,int l,int r,int node,int ml,int mr,int site)//对线段树更新 53 { 54 if(ml == l && mr == r && ml+1 == mr) 55 { 56 double area = (y[site+1] - y[site]) * (x[r] - x[l]); 57 58 if(area > st[node]) 59 { 60 double temp = area - st[node]; 61 st[node] = area; 62 return (temp); 63 } 64 else return 0; 65 } 66 67 int m = (l+r)/2; 68 69 if(mr <= m) 70 { 71 double area = change(st,l,m,node+node,ml,mr,site); 72 st[node] += area; 73 return area; 74 } 75 if(m <= ml) 76 { 77 double area = change(st,m,r,node+node+1,ml,mr,site); 78 st[node] += area; 79 return area; 80 } 81 82 double area = change(st,l,m,node+node,ml,m,site)+change(st,m,r,node+node+1,m,mr,site); 83 st[node] += area; 84 return area; 85 } 86 87 int main() 88 { 89 int n,icase = 1; 90 int i,j; 91 double area; 92 93 while(cin>>n && n) 94 { 95 for(i = 0,j = 0; i < n; i++) 96 { 97 cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2; 98 x[j] = a[i].x1; 99 y[j] = a[i].y1; 100 j++; 101 x[j] = a[i].x2; 102 y[j] = a[i].y2; 103 j++; 104 } 105 106 sort(x,x+j); 107 int sx = del(x,j); 108 sort(y,y+j); 109 int sy = del(y,j);//排序去掉重复点 110 111 for(i = 0;i <= sy; i++)//初始化线段树 112 { 113 memset(st[i],0,sizeof(st[i])); 114 } 115 116 for(area = 0,i = 0;i < n; i++) 117 { 118 int site_x1 = check_site(x,0,sx-1,a[i].x1);//查找对应编号 119 int site_y1 = check_site(y,0,sy-1,a[i].y1); 120 int site_x2 = check_site(x,0,sx-1,a[i].x2); 121 int site_y2 = check_site(y,0,sy-1,a[i].y2); 122 123 int temp; 124 if(site_x1 > site_x2) 125 { 126 temp = site_x1; 127 site_x1 = site_x2; 128 site_x2 = temp; 129 } 130 131 if(site_y1 > site_y2) 132 { 133 temp = site_y1; 134 site_y1 = site_y2; 135 site_y2 = temp; 136 } 137 138 for(j = site_y1;j < site_y2; j++)//每一棵线段树的第一个节点即为该段区域内的面积 139 { 140 area += change(st[j],0,sx-1,1,site_x1,site_x2,j);//area记录总面积 141 } 142 } 143 144 printf("Test case #%d\n",icase++); 145 printf("Total explored area: %.2lf\n\n",area); 146 } 147 return 0; 148 } View Code
换成这种矩阵模拟的办法也能过 时间和内存都有所减少 瞬间感觉自己丝毫没有窥探到线段树的精髓……sad
矩阵模拟的AC_code:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <cstdlib> 6 7 using namespace std; 8 9 double x[2200],y[2200]; 10 11 double st[2200][8000]; 12 13 struct N1 14 { 15 double x1,x2,y1,y2; 16 }a[1100]; 17 18 int del(double *t,int n)// 去掉重复点的函数 19 { 20 double s[2200]; 21 int top = 0,i; 22 for(i = 0;i < n; i++) 23 { 24 if(top == 0) 25 { 26 s[top++] = t[i]; 27 } 28 else if(t[i] != s[top-1]) 29 { 30 s[top++] = t[i]; 31 } 32 } 33 for(i = 0;i < top; i++) 34 { 35 t[i] = s[i]; 36 } 37 return top; 38 } 39 40 int check_site(double *t,int s,int e,double x)//二分查找当前点的对应编号 41 { 42 if(s == e) 43 return s; 44 int m = (s+e)/2; 45 if(x == t[m]) 46 return m; 47 if(x < t[m]) 48 return check_site(t,s,m-1,x); 49 else return check_site(t,m+1,e,x); 50 } 51 52 /*double change(double *st,int l,int r,int node,int ml,int mr,int site)//对线段树更新 53 { 54 if(ml == l && mr == r && ml+1 == mr) 55 { 56 double area = (y[site+1] - y[site]) * (x[r] - x[l]); 57 58 if(area > st[node]) 59 { 60 double temp = area - st[node]; 61 st[node] = area; 62 return (temp); 63 } 64 else return 0; 65 } 66 67 int m = (l+r)/2; 68 69 if(mr <= m) 70 { 71 double area = change(st,l,m,node+node,ml,mr,site); 72 st[node] += area; 73 return area; 74 } 75 if(m <= ml) 76 { 77 double area = change(st,m,r,node+node+1,ml,mr,site); 78 st[node] += area; 79 return area; 80 } 81 82 double area = change(st,l,m,node+node,ml,m,site)+change(st,m,r,node+node+1,m,mr,site); 83 st[node] += area; 84 return area; 85 }*/ 86 87 double change(int x1,int x2,int y1,int y2) 88 { 89 int i,j; 90 double area = 0; 91 for(i = y1;i < y2; i++) 92 { 93 for(j = x1;j < x2; j++) 94 { 95 if(st[i][j] == 0) 96 { 97 st[i][j] = (x[j+1]-x[j]) * (y[i+1]-y[i]); 98 area += st[i][j]; 99 } 100 } 101 } 102 return area; 103 } 104 105 int main() 106 { 107 int n,icase = 1; 108 int i,j; 109 double area; 110 111 while(cin>>n && n) 112 { 113 for(i = 0,j = 0; i < n; i++) 114 { 115 cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2; 116 x[j] = a[i].x1; 117 y[j] = a[i].y1; 118 j++; 119 x[j] = a[i].x2; 120 y[j] = a[i].y2; 121 j++; 122 } 123 124 sort(x,x+j); 125 int sx = del(x,j); 126 sort(y,y+j); 127 int sy = del(y,j);//排序去掉重复点 128 129 for(i = 0;i <= sy; i++)//初始化线段树 130 { 131 memset(st[i],0,sizeof(st[i])); 132 } 133 134 for(area = 0,i = 0;i < n; i++) 135 { 136 int site_x1 = check_site(x,0,sx-1,a[i].x1);//查找对应编号 137 int site_y1 = check_site(y,0,sy-1,a[i].y1); 138 int site_x2 = check_site(x,0,sx-1,a[i].x2); 139 int site_y2 = check_site(y,0,sy-1,a[i].y2); 140 141 int temp; 142 if(site_x1 > site_x2) 143 { 144 temp = site_x1; 145 site_x1 = site_x2; 146 site_x2 = temp; 147 } 148 149 if(site_y1 > site_y2) 150 { 151 temp = site_y1; 152 site_y1 = site_y2; 153 site_y2 = temp; 154 } 155 156 area += change(site_x1,site_x2,site_y1,site_y2); 157 158 /*for(j = site_y1;j < site_y2; j++)//每一棵线段树的第一个节点即为该段区域内的面积 159 { 160 area += change(st[j],0,sx-1,1,site_x1,site_x2,j);//area记录总面积 161 }*/ 162 } 163 164 printf("Test case #%d\n",icase++); 165 printf("Total explored area: %.2lf\n\n",area); 166 } 167 return 0; 168 } View Code
转载于:https://www.cnblogs.com/zmx354/archive/2013/06/04/3117896.html
