Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
附代码, 少加了个括号WA了一天QAQ#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> using namespace std; const int MAX = 10005; const double esp = 1e-5; struct point { double x, y; point ( ){ } point ( double _x, double _y ) { x = _x, y = _y; } point operator - ( const point &b ) { return point ( x - b.x, y - b.y ); } //向量叉积 double operator ^( const point &b ) { return x * b.y - y * b.x; } //向量点积 double operator *( const point &b ) { return x * b.x + y * b.y; } }; //将所有点变成逆时针(由于输入是逐点连线,输入顺序非逆即顺,因此只要判断若是顺时针逆置一下就好) void anticlockwise( point *p, int n ) { for( int i = 0; i < n - 2; i++ ) { double tmp = ( p[i] - p[i + 2] ) ^ ( p[i + 1] - p[i + 2] ); if( tmp > esp ) return; else if( tmp < -esp ) { reverse( p, p + n ); return; } } } //两点之间的距离公式 double dis( point a, point b ) { return ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ); } //点c到线段ab的距离 double p_s_dis( point c, point a, point b ) { point ab = b - a; point ac = c - a; double f = ab * ac; if( f < 0 ) return dis( a, c ); double t = ab * ab; if( f > t ) return dis( b, c ); f /= t; point d = point ( a.x + f * ab.x, a.y + f * ab.y ); return dis( d, c ); } //两线段之间的距离 double s_s_dis( point p1, point p2, point p3, point p4 ) { return min( min( p_s_dis( p1, p3, p4 ), p_s_dis( p2, p3, p4 )), min( p_s_dis( p3, p1, p2 ), p_s_dis( p4, p1, p2 ) ) ); } //rotating_calipers(旋转卡壳) double rc( point *a, point *b, int n, int m ) { int p = 0; int q = 0; for( int i = 0; i < n; i++ ) if( a[i].y - a[p].y < -esp ) p = i; for( int i = 0; i < m; i++ ) if( b[i].y - b[q].y > esp ) q = i; a[n] = a[0], b[m] = b[0]; double tmp, ans = 1e99; for( int i = 0; i < n; i++ ) { //注意,注意,注意,括号while后面有两个括号,这地方WA了一天,累觉不爱 QAQ; while( ( tmp = ( ( a[p + 1] - a[p] ) ^ ( b[q + 1] - a[p] ) ) - ( ( a[p + 1] - a[p] ) ^ ( b[q] - a[p] ) ) ) > esp ) q = ( q + 1 ) % m; if( tmp < -esp ) ans = min( ans, p_s_dis( b[q], a[p], a[p + 1] ) ); else ans = min( ans, s_s_dis( a[p], a[p + 1], b[q], b[q + 1] ) ); p = ( p + 1 ) % n; } return ans; } point pn[MAX], pm[MAX]; int main( ) { int m, n; while( cin>>n>>m ) { if( !n && !m ) break; for( int i = 0; i < n; i++ ) cin>>pn[i].x>>pn[i].y; for( int i = 0; i < m; i++ ) cin>>pm[i].x>>pm[i].y; anticlockwise( pn, n ); anticlockwise( pm, m ); //分别枚举两个凸包的边取较小值即可 printf( "%.5f\n", sqrt( min( rc( pn, pm, n, m ), rc( pm, pn, m, n ) ) ) ); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator