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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1337: 最小圆覆盖(随机增量法)  

2014-06-09 22:16:00|  分类: oi,bzoj,随机增量 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


随机增量法O(n)了事


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  • #include <cstdlib>

  •   

  • using namespace std ;

  •   

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

  •   

  • const int maxn = 100100 ;

  •   

  • typedef long double ld ;

  •   

  • const ld esp = 0.000000001 ;

  •   

  • ld sqr( ld x ) {

  •     return x * x ;

  • }

  •   

  • struct point {

  •     ld x , y ;

  •     void oper( ld _x , ld _y ) {

  •         x = _x , y = _y ;

  •     }

  •     ld dist( point p ) {

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

  •     }

  • } P[ maxn ] , p0 ;

  •   

  • int n ;

  • ld r ;

  •   

  • void cal( point a , point b , point c ) {

  •     ld a1 = 2 * ( b.x - a.x ) , b1 = 2 * ( b.y - a.y ) , c1 = sqr( b.x ) + sqr( b.y ) - sqr( a.x ) - sqr( a.y ) ;

  •     ld a2 = 2 * ( c.x - a.x ) , b2 = 2 * ( c.y - a.y ) , c2 = sqr( c.x ) + sqr( c.y ) - sqr( a.x ) - sqr( a.y ) ;

  •     p0.y = ( c1 * a2 - c2 * a1 ) / ( b1 * a2 - a1 * b2 ) ;

  •     p0.x = ( c1 - b1 * p0.y ) / a1 ;

  •     r = p0.dist( a ) ;

  • }

  •   

  • int main(  ) {

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

  •     rep( i , 1 , n ) {

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

  •         P[ i ].oper( ld( x ) , ld( y ) ) ;

  •     }

  •     random_shuffle( P + 1 , P + n + 1 ) ;

  •     p0 = P[ 1 ] , r = 0 ;

  •     rep( i , 2 , n ) if ( p0.dist( P[ i ] ) > r - esp ) {

  •         p0.x = ( P[ i ].x + P[ 1 ].x ) / 2.0 , p0.y = ( P[ i ].y + P[ 1 ].y ) / 2.0 ;

  •         r = p0.dist( P[ i ] ) ;

  •         rep( j , 2 , i - 1 ) if ( p0.dist( P[ j ] ) > r - esp ) {

  •             p0.x = ( P[ i ].x + P[ j ].x ) / 2.0 , p0.y = ( P[ i ].y + P[ j ].y ) / 2.0 ;

  •             r = p0.dist( P[ j ] ) ;

  •             rep( k , 1 , j - 1 ) if ( p0.dist( P[ k ] ) > r - esp ) cal( P[ i ] , P[ j ] , P[ k ] ) ;

  •         }

  •     }

  •     printf( "%.3f\n" , double( r ) ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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