1298 圆与三角形
题目来源： HackerRank
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注
给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出”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

#include<iostream>
using namespace std;
struct Point  {
int x,y;
};
int is_inside(struct Point p1,struct Point o,double r)//判断点与圆的位置关系
{
    double dist1,dist2;
    dist1=(p1.x-o.x)*(p1.x-o.x)+(p1.y-o.y)*(p1.y-o.y);
    if (dist1>r*r) return -1;//点在圆外
    else if (dist1==r*r) return 0;//点在圆上
    else return 1;//点在圆内
}
int is_intersect(struct Point p1,struct  Point p2,struct Point o,double r)//判断线段是否与圆有交点
{
    if (is_inside(p1,o,r)+is_inside(p2,o,r)==-2)//如果两点都在圆外
    {
        double a,b,c,dist1,dist2,angle1,angle2;
        if (p1.x==p2.x)
            a=1,b=0,c=-p1.x;
        else if (p1.y==p2.y)
            a=0,b=1,c=-p1.y;
        else
        {
            a=p1.y-p2.y;
            b=p2.x-p1.x;
            c=p1.x*p2.y-p2.x*p1.y;
        }
        dist1=a*o.x+b*o.y+c;
        dist1*=dist1;
        dist2=(a*a+b*b)*r*r;
        if (dist1>dist2) return 0;
        angle1=(o.x-p1.x)*(p2.x-p1.x)+(o.y-p1.y)*(p2.y-p1.y);
        angle2=(o.x-p2.x)*(p1.x-p2.x)+(o.y-p2.y)*(p1.y-p2.y);
        if (angle1>0&&angle2>0) return 1;
        return 0;
    }
    else if (is_inside(p1,o,r)+is_inside(p2,o,r)!=2)//一点在圆外或上，一点在圆内或上
        return 1;
    else return 0;//两点都在圆内

}
int main()
{
    int n;
    double r;
    Point o,a,b,c;
    cin>>n;
    while(n--)
    {
        cin>>o.x>>o.y>>r;
        cin>>a.x>>a.y;
        cin>>b.x>>b.y;
        cin>>c.x>>c.y;
        if( is_intersect(a,b,o,r)||is_intersect(a,c,o,r)||is_intersect(b,c,o,r))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}