51 nod 1298 圆与三角形

题目链接：

http://www.51nod.com/Challenge/Problem.html#problemId=1298&judgeId=771202

1298 圆与三角形

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

 

                              

 

输入

第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）

输出

共T行，对于每组输入数据，相交输出"Yes"，否则输出"No"。

输入样例

2
0 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5

输出样例

Yes
No

注意，判断的是相离（有内包含）

点到线段的距离参考：

https://blog.csdn.net/love_phoebe/article/details/81112531

This is the code:

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EXP exp(1)
#define EPS 1e-8
#define MOD 1e9+7
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x7f7f7f7f      //2139062143
#define LL_INF 0x7f7f7f7f7f7f7f7f //9187201950435737471
const int dr[]= {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]= {-1, 1, 0, 0, -1, 1, -1, 1};
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。

bool checkCollineation(double x1,double y1,double x2,double y2,double x3,double y3) //判断三点共线
{
    if( (x1*y2-x2*y1)+(x2*y3-x3*y2)+(x3*y1-y3*x1) == 0 )
        return true;
    return false;
}

double getDistance(double x1,double y1,double x2,double y2) //求两点直接距离。
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double getNearestDistance(double x1,double y1,double x2,double y2,double x,double y) //求点到线段的最短距离。
{
    if(checkCollineation(x1,y1,x2,y2,x,y) )//如果共线
        return min(getDistance(x1,y1,x,y), getDistance(x2,y2,x,y));
    double cross=(x2-x1) * (x-x1) + (y2-y1) * (y-y1); // |AB| * |AC|*cos(x)
    if (cross<=0)  //积小于等于0，说明 角BAC 是直角或钝角
        return sqrt((x-x1) * (x-x1) + (y-y1) * (y-y1));

    double d2 = (x2-x1) * (x2-x1) + (y2-y1) * (y2-y1); // |AB|
    if (cross >= d2)  //角ABC是直角或钝角
        return sqrt((x-x2) * (x-x2) + (y-y2) * (y-y2) );

    //锐角三角形
    double r = cross/d2;
    double px = x1+(x2-x1) * r;  // C在 AB上的垂足点（px，py）
    double py = y1+(y2-y1) * r;
    return sqrt((x-px) * (x-px) + (y-py) * (y-py) ); //两点间距离公式
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        double x,y,r;              //圆心和半径
        double x1,y1,x2,y2,x3,y3;  //三角形三点坐标
        double dis1,dis2,dis3,dis4,dis5,dis6;
        scanf("%lf%lf%lf",&x,&y,&r);
        scanf("%lf%lf",&x1,&y1);
        scanf("%lf%lf",&x2,&y2);
        scanf("%lf%lf",&x3,&y3);
        dis1 = getDistance(x,y,x1,y1);               //点1到圆心的距离
        dis2 = getDistance(x,y,x2,y2);               //点2到圆心的距离
        dis3 = getDistance(x,y,x3,y3);               //点3到圆心的距离
        dis4 = getNearestDistance(x1,y1,x2,y2,x,y);  //圆心到点1点2组成线段的距离
        dis5 = getNearestDistance(x1,y1,x3,y3,x,y);  //圆心到点1点3组成线段的距离
        dis6 = getNearestDistance(x2,y2,x3,y3,x,y);  //圆心到点2点3组成线段的距离
        /*不用epsWA到死*/
        if(dis4-r>EPS && dis5-r>EPS && dis6-r>EPS)   //三点在圆外且圆心到三角形三边距离大于r，没交点
            printf("No\n");
        else if(dis1<r && dis2<r && dis3<r)          //三点在圆内,一定没有交点，
            printf("No\n");
        else
            printf("Yes\n");                         //三点中有在圆外的点，有在圆内的点。
    }
    return 0;
}