| ||||||||||
| 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