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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1038: [ZJOI2008]瞭望塔(半平面交)  

2014-03-16 22:04:00|  分类: oi,bzoj,半平面交 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


裸裸的半平面交,WA了N次之后实在感叹O2下的精度实在DT,改成long double之后还发现居然还可以输出-0的额。。。唉~


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  • #include <cmath>
  •    
  • using namespace std ;
  •    
  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
  • #define maxn 1010
  •    
  • typedef long double ld ;
  •    
  • const ld esp = 0.0000001 ;
  • const ld inf = ld( 0x7fffffff ) * ld( 0x7fffffff ) ;
  •    
  • struct point {
  •        
  •     ld x , y ;
  •        
  •     void oper( ld _x , ld _y ) {
  •         x = _x , y = _y ;
  •     }
  •        
  • } p[ maxn ] , pos[ maxn ] ;
  •    
  • struct line {
  •        
  •     ld k , b ;
  •        
  •     void oper( point x , point y ) {
  •         k = ( x.y - y.y ) / ( x.x - y.x ) ;
  •         b = x.y - k * x.x ;
  •     }
  •        
  •     point cross( line l ) {
  •         point rec ;
  •         rec.x = - ( b - l.b ) / ( k - l.k ) ;
  •         rec.y = cal( rec.x ) ;
  •         return rec ;
  •     }
  •        
  •     ld cal( ld x ) {
  •         return k * x + b ;
  •     }
  •        
  •     bool operator < ( const line &a ) const {
  •         return k < a.k || ( k == a.k && b > a.b ) ;
  •     }
  •        
  • } li[ maxn ] , st[ maxn ] ;
  •    
  • int n , m = 0 , Top = 0 , M = 0 ;
  •     
  • ld calh( ld x , int left , int right , point *ret ) {
  •     if ( abs( ret[ left ].x - x ) < esp ) return ret[ left ].y ;
  •     if ( abs( ret[ right ].x - x ) < esp ) return ret[ right ].y ;
  •     while ( right - left > 1 ) {
  •         int mid = ( left + right ) >> 1 ;
  •         if ( abs( ret[ mid ].x - x ) < esp ) return ret[ mid ].y ;
  •         if ( x < ret[ mid ].x ) right = mid ; else left = mid ;
  •     }
  •     line temp ;
  •     temp.oper( ret[ left ] , ret[ right ] ) ;
  •     return temp.cal( x ) ;
  • }
  •    
  • ld calheight( ld x ) {
  •     ld h1 = calh( x , 1 , M , pos ) , h2 = calh( x , 1 , n , p ) ;
  •     return h1 - h2 ;
  • }
  •    
  • int main(  ) {
  •     scanf( "%d" , &n ) ;
  •     rep( i , n ) {
  •         double x ; scanf( "%lf" , &x ) ;
  •         p[ i ].x = ld( x ) ;
  •     }
  •     rep( i , n ) {
  •         double y ; scanf( "%lf" , &y ) ;
  •         p[ i ].y = ld( y ) ;
  •     }
  •     rep( i , n - 1 ) li[ ++ m ].oper( p[ i ] , p[ i + 1 ] ) ;
  •     sort( li + 1 , li + m + 1 ) ;
  •     rep( i , m ) {
  •         if ( abs( li[ i ].k - li[ i - 1 ].k ) <= esp ) continue ;
  •         while ( Top > 1 ) {
  •             point temp = st[ Top ].cross( li[ i ] ) ;
  •             if ( st[ Top - 1 ].cal( temp.x ) >= temp.y ) -- Top ;
  •             else break ;
  •         }
  •         st[ ++ Top ] = li[ i ] ;
  •     } 
  •     rep( i , Top ) {
  •         point temp = st[ i ].cross( st[ i + 1 ] ) ;
  •     }
  •     int left = 1 , right = Top ;
  •     while ( left < right ) {
  •         point temp = st[ left ].cross( st[ left + 1 ] ) ;
  •         if ( temp.x <= p[ 1 ].x ) ++ left ; else break ;
  •     }
  •     while ( left < right ) {
  •         point temp = st[ right ].cross( st[ right - 1 ] ) ;
  •         if ( temp.x >= p[ n ].x ) -- right ; else break ;
  •     }
  •     pos[ ++ M ].oper( p[ 1 ].x , st[ left ].cal( p[ 1 ].x ) ) ;
  •     for ( int i = left ; i < right ; ++ i ) {
  •         pos[ ++ M ] = st[ i ].cross( st[ i + 1 ] ) ;
  •     }
  •     pos[ ++ M ].oper( p[ n ].x , st[ right ].cal( p[ n ].x ) ) ;
  •     ld ans = inf ;
  •     rep( i , M ) ans = min( ans , calheight( pos[ i ].x ) ) ;
  •     rep( i , n ) ans = min( ans , calheight( p[ i ].x ) ) ;
  •     printf( "%.3f\n" , double( ans + esp ) ) ;
  •     return 0 ;
  • }



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

历史上的今天

评论

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

页脚

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