UVa 10180 - Rope Crisis in Ropeland!

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1121

题意：给出两点坐标，用一条最短的线（曲线或者直线）连接起来，坐标系中原点处有一个半径为R的圆，连线不能穿过这个圆。

分析：

这题我WA了好几次，原因是把double的坐标搞成int了，o(╯□╰)o

#include <cstdio>
#include <cstdlib>
#include <cmath>

const double PI = acos( -1.0 );

struct point
{
    double x, y;
};

point O;  //坐标原点

double Get_Dist( point &a, point &b )    //计算两点间距离
{
    return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y )*(a.y - b.y) );
}

double Get_Angle( double a, double b, double c )  //余弦定理求角度
{
    return acos( (b*b + c*c - a*a) / (2*b*c) );
}

bool check( point &m, point &n, double x, double y )  //判断坐标( x, y )是否在点 m, n 之间
{
    double minx = m.x < n.x ? m.x : n.x;
    double maxx = m.x > n.x ? m.x : n.x;
    double miny = m.y < n.y ? m.y : n.y;
    double maxy = m.y > n.y ? m.y : n.y;
    return ( x > minx && x <= maxx && y >= miny && y <= maxy );
}

bool Judge( point &m, point &n, double &R )           //判断是否需要绕过圆
{
    if ( m.x == n.x )                                 //特判与y轴平行的线
    {
        if ( abs(m.x) >= R ) return true;
        else
        {
            if ( m.y * n.y > 0 ) return true;
            else return false;
        }
    }
    else if ( m.y == n.y )                             //特判与x轴平行的线
    {
        if ( abs(m.y) >= R ) return true;
        else
        {
            if ( m.x * n.x > 0 ) return true;
            else return false;
        }
    }

    double A = n.y - m.y;                              //两点连成的直线，求直线方程一般式，计算A, B, C
    double B = m.x - n.x;
    double C = (n.x - m.x) * m.y - (n.y - m.y) * m.x;
    double dis = abs(C)/ sqrt( A*A + B*B );            //原点到直线的距离
    if ( dis >= R ) return true;
    else
    {
        double kkk = (-A) / B;
        double bbb = (-C) / B;
        double xx = ( -bbb ) / ( kkk + 1.0 / kkk );
        double yy = ( (-1.0) / kkk ) * xx;
        if ( check( m, n, xx, yy ) ) return false;     //如果线段穿过圆
        else return true;                              //如果线段不穿过圆
    }
}

int main()
{
    int T;
    double R;
    point A, B;
    O.x = 0;
    O.y = 0;
    scanf( "%d", &T );
    while ( T-- )
    {
        scanf( "%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &R );

        if ( Judge(A, B, R) )                             //如果不需要绕过圆
            printf( "%.3f\n", Get_Dist(A, B) );
        else                                              //如果需要绕过圆
        {
            double L1 = Get_Dist(A, O);
            double L2 = Get_Dist(B, O);
            double LL1 = sqrt( L1*L1 - R*R );
            double LL2 = sqrt( L2*L2 - R*R );
            double angle = Get_Angle( Get_Dist(A, B), L1, L2 ) - acos( R/L1 ) - acos( R/L2 );
            double ans = LL1 + LL2 + R * angle;
            printf( "%.3f\n", ans );
        }
    }
    return 0;
}