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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2433: [Noi2011]智能车比赛(最短路)  

2014-06-02 15:39:00|  分类: oi,bzoj,计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


我们可以YY出必定存在最短路仅由S,T,和公共点之间的直线连边构成,那么就每次对于一个点,求出其到右边所有点之间的可行连边,这个可以维护两个斜率上下界,为了保证精度,使用向量来表示,然后要是S在右边,那就和T交换一下,最后最短路一次即可,O(n^2 + n^2 log n)


代码(计算几何太弱了,调了整整两个小时QaQ):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <queue>

  • #include <cmath>

  • #include <vector>

  •  

  • using namespace std ;

  •  

  • #define travel( x ) for ( vector < edge > :: iterator p = E[ x ].begin(  ) ; p != E[ x ].end(  ) ; ++ p )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define addedge( s , t , d ) E[ s ].push_back( edge( t , d ) )

  •  

  • const int maxn = 2010 , maxv = 4010  , inf = 0x7fffffff ;

  • const double esp = 0.0000000000001 ;

  •  

  • inline int cmp( double x , double y ) {

  •     return y - x > esp ? -1 : ( x - y > esp ) ;

  • }

  •  

  • struct edge {

  •     int t ; double d ;

  •     edge( int _t , double _d ) : t( _t ) , d( _d ) {

  •     }

  • } ;

  • vector < edge > E[ maxv ] ;

  •  

  • double dist[ maxv ] ;

  • bool f[ maxv ] ;

  • int S , T , V = 0 , node[ maxn ][ 2 ] ;

  •  

  • struct Cmp {

  •     bool operator (  ) ( int x , int y ) {

  •         return dist[ x ] > dist[ y ] ;

  •     }

  • } ;

  • priority_queue < int , vector < int > , Cmp > q ;

  •  

  • inline double dijkstra(  ) {

  •     rep( i , V ) dist[ i ] = inf , f[ i ] = true ;

  •     dist[ S ] = 0 , q.push( S ) ;

  •     int now ; double cost ;

  •     while ( ! q.empty(  ) ) {

  •         now = q.top(  ) ; q.pop(  ) ;

  •         if ( ! f[ now ] ) continue ;

  •         f[ now ] = false ;

  •         if ( now == T ) return dist[ T ] ;

  •         travel( now ) if ( cmp( dist[ p -> t ] , cost = dist[ now ] + p -> d ) == 1 ) {

  •             dist[ p -> t ] = cost , f[ p -> t ] = true , q.push( p -> t ) ;

  •         }

  •     }

  •     return dist[ T ] ;

  • }

  •  

  • struct Point {

  •     double x , y ;

  •     void Read(  ) {

  •         scanf( "%lf%lf" , &x , &y ) ;

  •     }

  • } ;

  •  

  • struct Vector {

  •     double x , y ;

  •     Vector( double _x , double _y ) : x( _x ) , y( _y ) {

  •     }

  • } ;

  •  

  • Vector operator - ( const Point &a , const Point &b ) {

  •     return Vector( a.x - b.x , a.y - b.y ) ;

  • }

  •  

  • double operator * ( const Vector &a , const Vector &b ) {

  •     return a.x * b.y - b.x * a.y ;

  • }

  •  

  • inline double sqr( double val ) {

  •     return val * val ;

  • }

  •  

  • inline double Dist( const Point &a , const Point &b ) {

  •     return sqrt( sqr( a.x - b.x ) + sqr( a.y - b.y ) ) ;

  • }

  •  

  • Point st , to , pos[ maxn ][ 2 ] , px[ maxn ][ 2 ] ;

  • double sp , ans ;

  • int n , ps = 0 , pt = 0 ;

  •  

  • inline void make_edge( Point P , int N , int M ) {

  •     Vector L = Vector( 0 , 1 ) , R = Vector( 0 , -1 ) ;

  •     REP( i , N , pt ) {

  •         if ( cmp( ( px[ i ][ 0 ] - P ) * L , 0 ) != -1 && cmp( R * ( px[ i ][ 0 ] - P ) , 0 ) != -1 ) {

  •             addedge( M , node[ i ][ 0 ] , Dist( P , px[ i ][ 0 ] ) ) ;

  •             L = ( px[ i ][ 0 ] - P ) ;

  •         } else if ( cmp( ( px[ i ][ 0 ] - P ) * R , 0 ) == 1 ) break ;

  •         if ( cmp( ( px[ i ][ 1 ] - P ) * L , 0 ) != -1 && cmp( R * ( px[ i ][ 1 ] - P ) , 0 ) != -1 ) {

  •             addedge( M , node[ i ][ 1 ] , Dist( P , px[ i ][ 1 ] ) ) ;

  •             R = ( px[ i ][ 1 ] - P ) ;

  •         } else if ( cmp( L * ( px[ i ][ 1 ] - P ) , 0 ) == 1 ) break ;

  •     }

  • }

  •  

  • int main(  ) {

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

  •     rep( i , n ) pos[ i ][ 0 ].Read(  ) , pos[ i ][ 1 ].Read(  ) ;

  •     st.Read(  ) ; to.Read(  ) ; scanf( "%lf" , &sp ) ;

  •     if ( st.x > to.x ) swap( st , to ) ;

  •     rep( i , n ) {

  •         if ( ! ps ) {

  •             if ( cmp( st.x , pos[ i ][ 0 ].x ) != -1 && cmp( st.x , pos[ i ][ 1 ].x ) != 1 && cmp( st.y , pos[ i ][ 0 ].y ) != -1 && cmp( st.y , pos[ i ][ 1 ].y ) != 1 ) {

  •                 ps = i ;

  •             }

  •         }

  •         if ( ! pt ) {

  •             if ( cmp( to.x , pos[ i ][ 0 ].x ) != -1 && cmp( to.x , pos[ i ][ 1 ].x ) != 1 && cmp( to.y , pos[ i ][ 0 ].y ) != -1 && cmp( to.y , pos[ i ][ 1 ].y ) != 1 ) {

  •                 pt = i ;

  •             }

  •         }

  •     }

  •     if ( ps == pt ) ans = Dist( st , to ) ; else {

  •         REP( i , ps , ( pt - 1 ) ) {

  •             px[ i ][ 0 ].x = px[ i ][ 1 ].x = pos[ i ][ 1 ].x ;

  •             px[ i ][ 0 ].y = min( pos[ i ][ 1 ].y , pos[ i + 1 ][ 1 ].y ) ;

  •             px[ i ][ 1 ].y = max( pos[ i ][ 0 ].y , pos[ i + 1 ][ 0 ].y ) ;

  •         }

  •         px[ pt ][ 0 ] = px[ pt ][ 1 ] = to ;

  •         REP( i , ps , ( pt - 1 ) ) {

  •             node[ i ][ 0 ] = ++ V , node[ i ][ 1 ] = ++ V ;

  •         }

  •         S = ++ V , node[ pt ][ 0 ] = node[ pt ][ 1 ] = T = ++ V ;

  •         make_edge( st , ps , S ) ;

  •         REP( i , ps , ( pt - 1 ) ) {

  •             make_edge( px[ i ][ 0 ] , i , node[ i ][ 0 ] ) , make_edge( px[ i ][ 1 ] , i , node[ i ][ 1 ] ) ;

  •         }

  •         ans = dijkstra(  ) ;

  •     }

  •     printf( "%.10f\n" , ans / sp ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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