题目：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 ;
}
网友评论