Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

附代码, 少加了个括号WA了一天QAQ

Posted by litianci1223 at 2017-08-22 23:35:31 on Problem 3608
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator