51 nod 1298 圆与三角形 （计算几何）

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

思路：分析三角形和圆的位置关系可知非常复杂。
简化问题用从对立事件角度考虑。我们知道当圆与三角形不相交的情况有：
1）三角形的三点都在圆内，即圆心到三条边的距离都小于半径R；
2）当三角形的三点都在圆外时，只有圆心到三条边的距离都大于半径R时才满足不相交。

其余的情况都是相交。

这里还要解决的一个问题就是如何求圆心到三条边的距离？
利用海伦公式，p=(a+b+c)/2;S=sqrt(p*(p-a)*(p-b)*(p-c))；-->S=h*d/2;
把三角形上的两个点与圆心看成一个三角形，通过这个三角形的面积来求出圆心到这条边的距离。

#include<bits/stdc++.h>
#define M 1e-6
using namespace std;
double dis1(double a,double b,double x,double y)
{
    return sqrt((a-x)*(a-x)+(b-y)*(b-y));
}
double dis2(double a1,double b1,double a2,double b2,double x,double y)
{
    double a=dis1(a1,b1,x,y);
    double b=dis1(a2,b2,x,y);
    double c=dis1(a1,b1,a2,b2);
    if(a*a>=b*b+c*c)
        return b;
    else if(b*b>=a*a+c*c)
        return a;
    double p=(a+b+c)/2;
    double s=sqrt(p*(p-a)*(p-b)*(p-c));
    return s*2/c;///海伦公式 利用圆心与三角形的两点形成的三角形来求圆心到边的距离
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        double x,y,r;
        double a1,b1,a2,b2,a3,b3;
        double d1,d2,d3,d4,d5,d6;
        cin>>x>>y>>r;
        cin>>a1>>b1;
        cin>>a2>>b2;
        cin>>a3>>b3;
        d1=dis1(a1,b1,x,y);
        d2=dis1(a2,b2,x,y);
        d3=dis1(a3,b3,x,y);///三点到圆心的距离
        d4=dis2(a1,b1,a2,b2,x,y);
        d5=dis2(a1,b1,a3,b3,x,y);
        d6=dis2(a2,b2,a3,b3,x,y);///求圆心到三边的距离
        if(d4-r>M&&d5-r>M&&d6-r>M)
            printf("No\n");
        else if(d1<r&&d2<r&&d3<r)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}