注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

2300: [HAOI2011]防线修建(平衡树动态维护凸包)  

2014-03-02 20:47:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2300


刚开始看到删点不好操作,那么离线,然后变成加点,然后平衡树动态维护凸包来搞。


代码(SBT):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define update( t ) S( t ) = S( L( t ) ) + S( R( t ) ) + 1

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define K( t ) key[ t ]

  • #define S( t ) size[ t ]

  • #define pre( t ) prefix[ t ]

  • #define suff( t ) suffix[ t ]

  •  

  • #define dist( p0 , p1 ) ( sqrt( ( p0.x - p1.x ) * ( p0.x - p1.x ) + ( p0.y - p1.y ) * ( p0.y - p1.y ) ) )

  • #define cal( p0 , p1 ) ( ( p0.y - p1.y ) / ( p0.x - p1.x ) )

  • #define Clear( x ) memset( x , 0 , sizeof( x ) )

  •  

  • const double esp = 0.000000001 ;

  • const int maxn = 100100 ;

  • const int maxm = 200100 ;

  •  

  • struct node {

  •     double x , y ;

  •     void print(  ) {

  •         printf( "( %.3f , %.3f )\n" , x , y ) ;

  •     }

  •     bool operator < ( const node &a ) const {

  •         return x - a.x < - esp ;

  •     }

  •     bool operator == ( const node &a ) const {

  •         return abs( x - a.x ) <= esp ;

  •     }

  •     bool operator > ( const node &a ) const {

  •         return x - a.x > esp ;

  •     }

  • } key[ maxn ] ;

  •  

  • node make( double _x , double _y ) {

  •     node u ;

  •     u.x = _x , u.y = _y ;

  •     return u ;

  • }

  •  

  • int left[ maxn ] , right[ maxn ] , size[ maxn ] , prefix[ maxn ] , suffix[ maxn ] , V , roof ;

  •  

  • int q[ maxm ][ 2 ] , n , m ;

  • double pos[ maxn ][ 2 ] , px , py , ans[ maxm ] , rec , h ;

  • bool f[ maxn ] ;

  •  

  • void Left( int &t ) {

  •     int k = R( t ) ;

  •     R( t ) = L( k ) ; update( t ) ;

  •     L( k ) = t ; update( k ) ;

  •     t = k ;

  • }

  •  

  • void Right( int &t ) {

  •     int k = L( t ) ;

  •     L( t ) = R( k ) ; update( t ) ;

  •     R( k ) = t ; update( k ) ;

  •     t = k ;

  • }

  •  

  • void maintain( int &t ) {

  •     if ( S( L( L( t ) ) ) > S( R( t ) ) ) {

  •         Right( t ) ;

  •         maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( R( L( t ) ) ) > S( R( t ) ) ) {

  •         Left( L( t ) ) ; Right( t ) ;

  •         maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( R( R( t ) ) ) > S( L( t ) ) ) {

  •         Left( t ) ;

  •         maintain( L( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( L( R( t ) ) ) > S( L( t ) ) ) {

  •         Right( R( t ) ) ; Left( t ) ;

  •         maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  • }

  •  

  • void Insert( node k , int &t ) {

  •     if ( ! t ) {

  •         t = ++ V ;

  •         S( t ) = 1 , K( t ) = k ;

  •         return ;

  •     }

  •     Insert( k , k < K( t ) ? L( t ) : R( t ) ) ;

  •     update( t ) ; maintain( t ) ;

  • }

  •  

  • void Delete( node k , int &t ) {

  •     if ( k == K( t ) ) {

  •         if ( ! L( t ) ) {

  •             t = R( t ) ; return ;

  •         } else if ( ! R( t ) ) {

  •             t = L( t ) ; return ;

  •         } else {

  •             Right( t ) ; Delete( k , R( t ) ) ;

  •         }

  •     } else Delete( k , k < K( t ) ? L( t ) : R( t ) ) ;

  •     update( t ) ; maintain( t ) ;

  • }

  •  

  • int Prefix( node k ) {

  •     int ret = 0 ;

  •     for ( int t = roof ; t ; t = k < K( t ) ? L( t ) : R( t ) ) if ( K( t ) < k ) {

  •         if ( ! ret || K( ret ) < K( t ) ) ret = t ;

  •     }

  •     return ret ;

  • }

  •  

  • int Suffix( node k ) {

  •     int ret = 0 ;

  •     for ( int t = roof ; t ; t = k < K( t ) ? L( t ) : R( t ) ) if ( K( t ) > k ) {

  •         if ( ! ret || K( ret ) > K( t ) ) ret = t ;

  •     }

  •     return ret ;

  • }

  •  

  • int Find( node k ) {

  •     for ( int t = roof ; t ; t = k < K( t ) ? L( t ) : R( t ) ) if ( K( t ) == k ) return t ;

  •     return 0 ;

  • }

  •  

  • void Push( node k ) {

  •     int t = Find( k ) ;

  •     if ( t ) {

  •         if ( K( t ).y >= k.y ) return ;

  •         rec -= ( dist( K( pre( t ) ) , K( t ) ) + dist( K( suff( t ) ) , K( t ) ) ) ;

  •         rec += dist( K( pre( t ) ) , K( suff( t ) ) ) ;

  •         suff( pre( t ) ) = suff( t ) , pre( suff( t ) ) = pre( t ) ;

  •         Delete( K( t ) , roof ) ;

  •     }

  •     int tp = Prefix( k ) , ts = Suffix( k ) ;

  •     if ( cal( K( tp ) , k ) <= cal( K( tp ) , K( ts ) ) ) return ;

  •     rec -= dist( K( tp ) , K( ts ) ) ;

  •     while ( K( tp ).x > esp ) {

  •         if ( cal( K( pre( tp ) ) , K( tp ) ) <= cal( K( tp ) , k ) ) {

  •             rec -= dist( K( pre( tp ) ) , K( tp ) ) ;

  •             Delete( K( tp ) , roof ) ;

  •         } else break ;

  •         tp = pre( tp ) ;

  •     }

  •     while ( h - K( ts ).x > esp ) {

  •         if ( cal( K( suff( ts ) ) , K( ts ) ) >= cal( K( ts ) , k ) ) {

  •             rec -= dist( K( suff( ts ) ) , K( ts ) ) ;

  •             Delete( K( ts ) , roof ) ;

  •         } else break ;

  •         ts = suff( ts ) ;

  •     }

  •     Insert( k , roof ) ;

  •     pre( suff( tp ) = V ) = tp , suff( pre( ts ) = V ) = ts ;

  •     rec += ( dist( K( tp ) , k ) + dist( K( ts ) , k ) ) ;

  • }

  •  

  • void Test( int t ) {

  •     for ( t = roof ; L( t ) ; t = L( t ) ) ;

  •     for ( ; t ; t = suff( t ) ) K( t ).print(  ) ;

  • }

  •  

  • int main(  ) {

  •     scanf( "%lf%lf%lf" , &h , &px , &py ) ;

  •     scanf( "%d" , &n ) ;

  •     memset( f , true , sizeof( f ) ) ;

  •     for ( int i = 0 ; i ++ < n ; ) scanf( "%lf%lf" , &pos[ i ][ 0 ] , &pos[ i ][ 1 ] ) ;

  •     scanf( "%d" , &m ) ;

  •     for ( int i = 0 ; i ++ < m ; ) {

  •         scanf( "%d" , &q[ i ][ 0 ] ) ;

  •         if ( q[ i ][ 0 ] == 1 ) {

  •             scanf( "%d" , &q[ i ][ 1 ] ) ;

  •             f[ q[ i ][ 1 ] ] = false ;

  •         }

  •     }

  •     Clear( left ) , Clear( right ) , Clear( size ) ;

  •     V = 3 ;

  •     S( roof = 2 ) = 3 ; K( roof ) = make( px , py ) , L( roof ) = pre( roof ) = 1 , R( roof ) = suff( roof ) = 3 ;

  •     S( 1 ) = S( 3 ) = 1 , suff( 1 ) = pre( 3 ) = 2 , K( 1 ) = make( 0 , 0 ) , K( 3 ) = make( h , 0 ) ;

  •     rec = dist( make( 0 , 0 ) , make( px , py ) ) + dist( make( px , py ) , make( h , 0 ) ) ;

  •     for ( int i = 0 ; i ++ < n ; ) if ( f[ i ] ) Push( make( pos[ i ][ 0 ] , pos[ i ][ 1 ] ) ) ;

  •     for ( int i = m ; i ; -- i ) {

  •         if ( q[ i ][ 0 ] == 1 ) {

  •             Push( make( pos[ q[ i ][ 1 ] ][ 0 ] , pos[ q[ i ][ 1 ] ][ 1 ] ) ) ;

  •         } else {

  •             ans[ i ] = rec ;

  •         }

  • //      printf( "\n\n%d:\n" , i ) ;

  • //      Test( roof ) ;

  •     }

  •     for ( int i = 0 ; i ++ < m ; ) if ( q[ i ][ 0 ] == 2 ) printf( "%.2f\n" , ans[ i ] ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017