首页 > 代码库 > hdu--1542&&1255--线段树<扫描线>
hdu--1542&&1255--线段树<扫描线>
所谓扫描线一般按照习惯上 就是说从左到右 或者是 从下到上
这2题 都是这样的运用 但除此 也还有别的方法可以过
我们将下边标记为1 上边标记为-1 这是自下而上的扫描 如果是从左到右 那么自然是左边为1 右边为-1
这边 当然要进行离散化了。 因为是数据蛮大的浮点数嘛~
这步真的很重要= =
然后注意下 unique去重 或者自己手写for遍历一遍 我就懒的写了
直接Lower_bound就可以了 因为这些数据肯定能找到的嘛
这边 线段树的建树需要注意下 因为我们的叶子结点是 1-2 2-3这样的元线段 所以这边我们建立的不是通常我们所建立的1-1 2-2这样的。
其实我还是没有说到重点 就是对于该节点所表示的区间被覆盖一次 2次及以上 没覆盖 或者到达了叶子节点 我们究竟为什么是采取这些操作~
我们先来讲1542-求出矩形覆盖的所有面积<一个区域被覆盖2次 只计算一次>
艹。。。还是自己画图吧。。
但是有什么 不清楚的可以留言= =
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <iomanip> 5 using namespace std; 6 7 int cnt; 8 const int size = 220; 9 struct data 10 { 11 int L , R; 12 double x1 , x2 , y; 13 double sum; 14 int flag; 15 data(){}; 16 data( double u , double v , double w , int p ):x1(u),x2(v),y(w),flag(p){}; 17 }tree[size*4] , mat[size]; 18 double w[size]; 19 20 bool cmp( const data p , const data q ) 21 { 22 return p.y < q.y; 23 } 24 25 void pushUp( int rt ) 26 { 27 if( tree[rt].flag ) 28 tree[rt].sum = w[ tree[rt].R ] - w[ tree[rt].L ]; 29 else if( tree[rt].L+1==tree[rt].R ) 30 tree[rt].sum = 0; 31 else 32 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum; 33 } 34 35 void build( int rt , int L , int R ) 36 { 37 int M = ( L + R ) >> 1; 38 tree[rt].L = L; 39 tree[rt].R = R; 40 tree[rt].sum = 0; 41 tree[rt].flag = 0; 42 if( L+1==R ) 43 { 44 return ; 45 } 46 build( rt<<1 , L , M ); 47 build( rt<<1|1 , M , R ); 48 } 49 50 void update( int rt , int L , int R , int var )//var区别是上边还是下边 51 { 52 int M = ( tree[rt].L + tree[rt].R ) >> 1; 53 if( tree[rt].L == L && tree[rt].R == R ) 54 { 55 tree[rt].flag += var; 56 pushUp( rt ); 57 return ; 58 } 59 if( R<=M ) 60 update( rt<<1 , L , R , var ); 61 else if( L>=M ) 62 update( rt<<1|1 , L , R , var ); 63 else 64 { 65 update( rt<<1 , L , M , var ); 66 update( rt<<1|1 , M , R , var ); 67 } 68 pushUp( rt ); 69 } 70 71 int main() 72 { 73 int Case = 1 , n; 74 double x1 , y1 , x2 , y2; 75 double ans; 76 while( cin >> n && n ) 77 { 78 cnt = 1; 79 for( int i = 0 ; i<n ; i++ ) 80 { 81 cin >> x1 >> y1 >> x2 >> y2; 82 w[cnt] = x1; 83 mat[cnt++] = data( x1 , x2 , y1 , 1 ); 84 w[cnt] = x2; 85 mat[cnt++] = data( x1 , x2 , y2 , -1 ); 86 } 87 sort( w+1 , w+cnt );//离散化x轴坐标 88 sort( mat+1 , mat+cnt , cmp );//按y的高低来排 89 cnt = unique( w+1 , w+cnt ) - w; 90 build( 1 , 1 , cnt-1 ); 91 ans = 0; 92 for( int i = 1 ; i<(n<<1) ; i++ ) 93 { 94 int L = lower_bound( w+1 , w+cnt , mat[i].x1 ) - w; 95 int R = lower_bound( w+1 , w+cnt , mat[i].x2 ) - w; 96 update( 1 , L , R , mat[i].flag ); 97 ans += tree[1].sum * ( mat[i+1].y - mat[i].y ); 98 } 99 cout << "Test case #" << Case++ << endl;100 cout << "Total explored area: ";101 cout << setiosflags(ios::fixed);102 cout << setprecision(2) << ans << endl << endl;103 }104 return 0;105 }
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <iomanip> 5 using namespace std; 6 7 int cnt; 8 const int size = 2200; 9 struct data 10 { 11 int L , R; 12 double x1 , x2 , y; 13 double onceSum; 14 double twiceSum; 15 int flag; 16 data(){}; 17 data( double u , double v , double w , int p ):x1(u),x2(v),y(w),flag(p){}; 18 }tree[size*4] , mat[size]; 19 double w[size]; 20 21 bool cmp( const data p , const data q ) 22 { 23 return p.y < q.y; 24 } 25 26 void push( int rt ) 27 { 28 if( tree[rt].flag ) 29 tree[rt].onceSum = w[ tree[rt].R ] - w[ tree[rt].L ]; 30 else if( tree[rt].L +1 == tree[rt].R ) 31 tree[rt].onceSum = 0; 32 else 33 tree[rt].onceSum = tree[rt<<1].onceSum + tree[rt<<1|1].onceSum; 34 } 35 36 void pushUp( int rt ) 37 { 38 if( tree[rt].flag>=2 ) 39 tree[rt].twiceSum = w[ tree[rt].R ] - w[ tree[rt].L ]; 40 else if( tree[rt].L +1 == tree[rt].R ) 41 tree[rt].twiceSum = 0; 42 else if( tree[rt].flag==1 ) 43 tree[rt].twiceSum = tree[rt<<1].onceSum + tree[rt<<1|1].onceSum; 44 else 45 tree[rt].twiceSum = tree[rt<<1].twiceSum + tree[rt<<1|1].twiceSum; 46 } 47 48 void build( int rt , int L , int R ) 49 { 50 int M = ( L + R ) >> 1; 51 tree[rt].L = L; 52 tree[rt].R = R; 53 tree[rt].onceSum = tree[rt].twiceSum = 0; 54 tree[rt].flag = 0; 55 if( L+1==R ) 56 { 57 return ; 58 } 59 build( rt<<1 , L , M ); 60 build( rt<<1|1 , M , R ); 61 } 62 63 void update( int rt , int L , int R , int var )//var区别是上边还是下边 64 { 65 int M = ( tree[rt].L + tree[rt].R ) >> 1; 66 if( tree[rt].L == L && tree[rt].R == R ) 67 { 68 tree[rt].flag += var; 69 push( rt ); 70 pushUp( rt ); 71 return ; 72 } 73 if( R<=M ) 74 update( rt<<1 , L , R , var ); 75 else if( L>=M ) 76 update( rt<<1|1 , L , R , var ); 77 else 78 { 79 update( rt<<1 , L , M , var ); 80 update( rt<<1|1 , M , R , var ); 81 } 82 push( rt ); 83 pushUp( rt ); 84 } 85 86 int main() 87 { 88 int n , T; 89 double x1 , y1 , x2 , y2; 90 double ans; 91 while( ~scanf("%d",&T) ) 92 { 93 while( T-- ) 94 { 95 cnt = 1; 96 scanf("%d",&n); 97 for( int i = 0 ; i<n ; i++ ) 98 { 99 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);100 w[cnt] = x1;101 mat[cnt++] = data( x1 , x2 , y1 , 1 );102 w[cnt] = x2;103 mat[cnt++] = data( x1 , x2 , y2 , -1 );104 }105 sort( w+1 , w+cnt );//离散化x轴坐标 106 sort( mat+1 , mat+cnt , cmp );//按y的高低来排 107 cnt = unique( w+1 , w+cnt ) - w;108 build( 1 , 1 , cnt-1 );109 ans = 0;110 for( int i = 1 ; i<(n<<1) ; i++ )111 {112 int L = lower_bound( w+1 , w+cnt , mat[i].x1 ) - w;113 int R = lower_bound( w+1 , w+cnt , mat[i].x2 ) - w; 114 update( 1 , L , R , mat[i].flag );115 ans += tree[1].twiceSum * ( mat[i+1].y - mat[i].y );116 }117 //cout << setiosflags(ios::fixed);118 //cout << setprecision(2) << ans << endl;119 printf("%.2lf\n",ans);120 }121 }122 return 0;123 }
hdu--1542&&1255--线段树<扫描线>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。