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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1027: [JSOI2007]合金(最小环)  

2014-05-21 11:02:00|  分类: oi,bzoj,最小环, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


额。。。计算几何太弱了,这题搞了N久才A掉,就是用最小环求一下最小的凸包,然后记得要特判一下所有点都在一个点处的情况。。。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <queue>

  • #include <vector>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • const int inf = 1000000 ;

  • const double esp = 0.00000000001 ;

  • const int maxn = 510 ;

  •  

  • struct Point {

  •     double x , y ;

  •     void read(  ) {

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

  •     }

  • } p0[ maxn ] , p1[ maxn ] ;

  •  

  • struct Vector {

  •     double x , y ;

  • } ;

  •  

  • Vector operator - ( const Point &x , const Point &y ) {

  •     return ( Vector ) { x.x - y.x , x.y - y.y } ;

  • }

  •  

  • double operator * ( const Vector &x , const Vector &y ) {

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

  • }

  •  

  • double mul( const Vector &x , const Vector &y ) {

  •     return x.x * y.x + x.y * y.y ;

  • }

  •  

  • struct graph {

  •      

  •     vector < int > E[ maxn ] ;

  •     int V ;

  •      

  •     void Init( int _V ) {

  •         V = _V ;

  •     }

  •      

  •     void addedge( int s , int t ) {

  •         E[ s ].push_back( t ) ;

  •     }

  •      

  •     int dist[ maxn ] ;

  •     queue < int > q ;

  •      

  •     void bfs( int v ) {

  •         for ( int i = 0 ; i ++ < V ; ) dist[ i ] = inf ;

  •         for ( vector < int > :: iterator p = E[ v ].begin(  ) ; p != E[ v ].end(  ) ; ++ p ) {

  •             dist[ *p ] = 1 , q.push( *p ) ;

  •         }

  •         while ( ! q.empty(  ) ) {

  •             int now = q.front(  ) ; q.pop(  ) ;

  •             for ( vector < int > :: iterator p = E[ now ].begin(  ) ; p != E[ now ].end(  ) ; ++ p ) if ( dist[ now ] + 1 < dist[ *p ] ) {

  •                 dist[ *p ] = dist[ now ] + 1 ;

  •                 q.push( *p ) ;

  •             }

  •         }

  •     }

  •      

  • } g ;

  •  

  • int n , m ;

  •  

  • bool cmp( double x , double y ) {

  •     return abs( x - y ) < esp ;

  • }

  •  

  • int main(  ) {

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

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

  •         p0[ i ].read(  ) ;

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

  •     }

  •     bool flag = true ;

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

  •         p1[ i ].read(  ) ;

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

  •         if ( ! ( cmp( p1[ i ].x , p1[ 1 ].x ) && cmp( p1[ i ].y , p1[ 1 ].y ) ) ) flag = false ;

  •     }

  •     if ( flag ) {

  •         for ( int i = 0 ; i ++ < n ; ) if ( cmp( p0[ i ].x , p1[ 1 ].x ) && cmp( p0[ i ].y , p1[ 1 ].y ) ) {

  •             printf( "1\n" ) ;

  •             return 0 ;

  •         }

  •     }

  •     g.Init( n ) ;

  •     for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < n ; ) if ( i != j ) {

  •         Vector v = p0[ j ] - p0[ i ] ;

  •         flag = true ;

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

  •             double ret = v * ( p1[ k ] - p0[ i ] ) ;

  •             if ( ! ( ret > esp || ( ret > - esp && ret < esp && mul( p1[ k ] - p0[ i ] , p1[ k ] - p0[ j ] ) < esp ) ) ) {

  •                 flag = false ;

  •                 break ;

  •             }

  •         }

  •         if ( flag ) g.addedge( i , j ) ;

  •     }

  •     int ans = inf ;

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

  •         g.bfs( i ) ;

  •         ans = min( ans , g.dist[ i ] ) ;

  •     }

  •     printf( "%d\n" , ans < inf ? ans : -1 ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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