51 Nod-1298-円と三角形

ACMテンプレート
説明
円の中心と半径、三角形の3つの頂点を与えて、円と三角形が交差しているかどうかを尋ねます.交差出力「Yes」、そうでなければ出力「No」.(三角形の面積は0より大きい).
Input 1行目:入力されたテスト数(1<=T<=10000)を示す数T、その後4行ごとにテストデータのセットを記述する.4-1:3個の数、最初の2個の数が円心の座標xc,yc、3番目の数が円の半径Rである.(-3000<=xc,yc<=3000,1<=R<=3000)4-2:2個の数、三角形の1番目の点の座標.4-3:2個の数、三角形の2番目の点の座標.4-4:2個の数、三角形の3番目の点の座標.(-3000<=xi,yi<=3000)
OutputはT行で、入力データのセットごとに「Yes」、そうでなければ「No」を出力します.
Input例2 0 10 10 0 15 0 15 5 0 10 0 5 5 5 5 5
Output例Yes No
問題解
全体的に分析すると、3つの状況に分けられ、1つは点がすべて円内にある場合、NOを出力する.もう1つは3点がすべて円の外にあるので、この状況がポイントです.よく分析する必要があります(すべて円の外で交差するかどうかしか分からないため).最後に、他の場合のすべてが交差する場合、すなわちYesを出力します.では、2つ目の場合を分析すると、直観的に言えば、三角形の3つの辺に円と交差する点があるかどうかを判断し、問題は最後に線分が円と交差しているかどうかを判断することに変わります.
コード#コード#

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef struct  //     
{
    ll x, y;
} Point;

Point A, B, C, O;   //          
ll r;               //    

//          
ll distance(Point *p_1, Point *p_2)
{
    return (p_1->x - p_2->x) * (p_1->x - p_2->x) + (p_1->y - p_2->y) * (p_1->y - p_2->y);
}

//            
int segOnCircle(Point *p_1, Point *p_2)
{
    ll a, b, c, dist_1, dist_2, angle_1, angle_2;   //  ax + by + c = 0;
    if (p_1->x == p_2->x)                           //   x  
    {
        a = 1, b = 0, c = -p_1->x;
    }
    else if (p_1->y == p_2->y)                      //   y  
    {
        a = 0, b = 1, c = -p_1->y;
    }
    else
    {
        a = p_1->y - p_2->y;
        b = p_2->x - p_1->x;
        c = p_1->x * p_2->y - p_1->y * p_2->x;
    }
    dist_1 = a * O.x + b * O.y + c;
    dist_1 *= dist_1;
    dist_2 = (a * a + b * b) * r * r;
    if (dist_1 > dist_2)
    {
        return 0;
    }
    angle_1 = (O.x - p_1->x) * (p_2->x - p_1->x) + (O.y - p_1->y) * (p_2->y - p_1->y);
    angle_2 = (O.x - p_2->x) * (p_1->x - p_2->x) + (O.y - p_2->y) * (p_1->y - p_2->y);
    if (angle_1 > 0 && angle_2 > 0)
    {
        return 1;
    }
    return 0;
}

//        ，    1，    0
int intersect()
{
    ll distA = distance(&O, &A);    //  OA^2
    ll distB = distance(&O, &B);    //  OB^2
    ll distC = distance(&O, &C);    //  OC^2
    ll r2 = r * r;                  //  r^2
    if (distA < r2 && distB < r2 && distC < r2)         //        
    {
        return 0;
    }
    else if (distA > r2 && distB > r2 && distC > r2)    //        
    {
        return segOnCircle(&A, &B) || segOnCircle(&A, &C) || segOnCircle(&B, &C);   //        0，  ，  1
    }
    return 1;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld", &O.x, &O.y, &r, &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);
        printf("%s
", intersect() ? "Yes" : "No");
    }
    return 0;
}

リファレンス
線分と円が交差するかどうかを判断する