BZOJ-1027:|BZOJ-1027: [JSOI2007]合金（最小环）
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1027
额。。。计算几何太弱了，这题搞了N久才A掉，就是用最小环求一下最小的凸包，然后记得要特判一下所有点都在一个点处的情况。。。
【BZOJ-1027:|BZOJ-1027: [JSOI2007]合金（最小环）】代码：
#include #include #include #include #include #include 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 ;
}
推荐阅读
- 铝合金门窗设计安装之窗户尺寸篇
- 知合金服双十一福利（快乐双十一，你购物，我买单）
- 众安国际综合金融团队技术周报（第四期）
- (自适应手机端)自适应门窗定制pbootcms网站模板，铝合金门窗网站源码下载。
- 【玩转云函数】腾讯云云函数结合金山文档打造轻量级 Office 在线预览服务
- 青铜文明——青铜器的合金成分
- 【游戏文化】小岛秀夫何以封神（《死亡搁浅》真的吊打《合金装备》嘛？）
- 合金结构钢板42CrMo的简介/性能/工艺规范的详细介绍
- 诗‖|诗‖ 站在港口路的一片铝合金
- 铝合金汉子的一天