51nod_1298_圆与三角形

51nod_1298_圆与三角形

题目链接

题目描述

    给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出"Yes"，否则输出"No"。（三角形的面积大于0）。

Input

    第1行：一个数T，表示输入的测试数量(1 <= T <= 10000)，之后每4行用来描述一组测试数据。
    4-1：三个数，前两个数为圆心的坐标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 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5

Output示例

Yes
No

解题思路

判断三角形与圆是否有交
三种情况
一、三角形三顶点均在圆内，易知无交点
二、三角形三顶点均在圆外，需对三条边进行判断是否与圆相交
三、其他情况，易知有交点
至此，将此问题转化为如何判断线段与圆是否有交

判断线段与圆是否有交

AC代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct  //  点结构
{
    ll x, y;
} Point;

Point A, B, C, O;   //  三角形三点与圆心
ll r;               //  半径
//  判断线段是否和圆相交
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;
}
double get_dis(Point *p_1,Point *p_2) {
    return sqrt(pow(p_1->x - p_2->x, 2) + pow(p_1->y - p_2->y, 2));
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> O.x >> O.y >> r;
        cin >> A.x >> A.y;
        cin >> B.x >> B.y;
        cin >> C.x >> C.y;
        double la = get_dis(&O, &A);
        double lb = get_dis(&O, &B);
        double lc = get_dis(&O, &C);
        if (la < r&&lb < r&&lc < r) {
            cout << "No\n";
        }
        else if (la > r&&lb > r&&lc > r) {
            if (segOnCircle(&A, &B) || segOnCircle(&A, &C) || segOnCircle(&B, &C)) {
                cout << "Yes\n";
            }
            else {
                cout << "No\n";
            }
        }
        else {
            cout << "Yes\n";
        }
    }
    return 0;
}