题目链接：戳一戳

//文末附有90组测试数据

题目描述：

解题思路：

题意很清楚了，给你三角形三个顶点，圆心，半径。判断是否相交。

我们先列出所有的情况来看下：

1、首先最明显的，给你的这三个顶点如果存在某一个顶点就在圆上，那么三角形和圆肯定是相交的了。（这个也很好判断，把顶点坐标带入圆的方程，看是否等于 r*r 就好了）

2、如果所有的顶点都在圆内，三角形和圆肯定不相交。（判断方法同上，看是否小于 r*r）

3、如果三个点 有在圆外的 也有在圆内的，那么三角形和圆一定相交（判断方法同上）

4、那么就剩最后一种情况了，所有的点都在圆外。这种情况并不能直接确定是否相交，如下图

那么这种情况我们如何判断是否相交呢？看图大家也能观察的出来。三条线段只要有一条和圆相交就说明三角形和圆相交了。

所以问题就转化成了 “如何判断线段是否和圆相交的问题”

那么 我们学过距离公式可以求点到直线的距离  就像上图的（1） 我们套公式求出圆心到三个直线的距离，与半径一比较就知道相交不相交了。但是图（2）的情况就不适用于这种方法了  如图

我们求出的点到直线的距离 确实小于 r   但是三角形并不和圆相交  因为我们要判断的是圆心到线段的距离

那么怎么做呢？如何判断圆心是否于线段相交呢？

求出圆心到直线的距离  若大于R 那一定不相交 若距离小于R

再求出垂足的横坐标  若垂足的横坐标在线段两个端点的横坐标之间，那么相交，否则不相交。

 

到这里 整个题目的思路做法已经出来了，剩下的就是实现的问题了

实现起来还有几个小问题  是这个题需要注意的（没错 这才是坑点T_T）

首先先复习几个公式

已知两个点坐标我们就能算出斜率  公式

得到了斜率k   我们就可以用     y=kx+b   (直线的点斜式方程)

还有一个性质  两直线垂直 斜率之积等于 -1

1、如何求出垂足坐标

由线段的两个点我们可以求出线段所在直线的斜率，以及点斜式方程。然后垂足和圆心所在的直线是和他们垂直的，所以斜率之积等于-1。求得斜率，然后还知道圆心的坐标，就可以求出点斜式方程。两个直线的方程出来了，联立就可以解出来交点的横坐标了。

2、斜率的问题

有三种情况很特殊，线段平行于x轴（斜率不存在），线段平行于y轴（斜率=0）。 这两种情况，我们要先做特殊判断。

当线段平行于x轴的时候。线段到圆心距离很好算，纵坐标相减就行了（取绝对值）。那垂足在不在线段上，也很好判断，看圆心的横坐标在不在线段两个端点范围内就行了。平行于y轴同理。

还有一种，线段所在的直线过圆心。这种情况我看到有的博客上写要特殊判断，但是我的这个方法不需要特殊判断。这种情况用我的方法，会算出圆心到直线的距离是0，也会解出垂足的横坐标（就是圆心的横坐标），然后和端点比较就行了。

3、比较相等的问题

这题输入的数据是double  double是不能直接判断相等的 需要相减判精度 注意一下

4、取绝对值问题

程序中很多地方判断距离用坐标相减，都需要做取绝对值操作。注意一下（因为这个wa了两遍）

AC代码及详细注释：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=1007;
const int INF=0x3f3f3f3f;
const double decimal=0.00001;
pair<double,double> y,d1,d2,d3;
double r;
double dis(pair<double,double> a,pair<double,double> b){
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
bool Line_Round(pair<double,double> a,pair<double,double> b){
    //要先考虑直线平行于x轴或者y轴的情况 因为平行于x轴 斜率是不存在的
    //直线平行于x轴
    if(fabs(a.second-b.second)<decimal){
        if(fabs(a.second-y.second)>r)return false;
        if(y.first<=max(a.first,b.first)&&y.first>=min(a.first,b.first))return true;
        else return false;
    }
    //直线平行于y轴
    if(fabs(a.first-b.first)<decimal){
        if(fabs(a.first-y.first)>r)return false;
        if(y.second<=max(a.second,b.second)&&y.second>=min(a.second,b.second))return true;
        else return false;
    }
    //不平行与x和y
    double k=(b.second-a.second)/(b.first-a.first);//计算斜率
    double bb=a.second-k*a.first;//公式中的b
    double dd=fabs( (k*y.first-y.second+bb)/sqrt(k*k+1) );//圆心到直线距离
    if(dd>r)return false;//圆心到直线的距离大于r 线段与圆不相交
    //圆心到直线的距离小于等于r
    double k2=-1/k;
    double bb2=y.second-k2*y.first;
    double cz_x=(bb2-bb)/(k-k2);//计算垂足的横坐标
    if(cz_x<=max(a.first,b.first)&&cz_x>=min(a.first,b.first))return true;
    else return false;
}
bool check(){
    double a=dis(d1,y),b=dis(d2,y),c=dis(d3,y);

    //如果有点在圆上 那么肯定相交
    if(fabs(a-r*r)<decimal||fabs(b-r*r)<decimal||fabs(c-r*r)<decimal)return true;

    //如果都在圆内 一定不相交
    if(a<r*r&&b<r*r&&c<r*r)return false;

    //如果圆内有点 圆外也有点 那么一定相交
    bool n=false,w=false;
    if(a<r*r||b<r*r||c<r*r)n=true;
    if(a>r*r||b>r*r||c>r*r)w=true;
    if(n&&w)return true;
    //所有的点都在圆外
    if(Line_Round(d1,d2)||Line_Round(d1,d3)||Line_Round(d2,d3))return true;
    else return false;
}
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%lf%lf%lf",&y.first,&y.second,&r);
        scanf("%lf%lf%lf%lf%lf%lf",&d1.first,&d1.second,&d2.first,&d2.second,&d3.first,&d3.second);
        if(check())printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

附上test3

30
9 3 7
-1 -3
5 -6
4 8
3 1 9
-2 -10
0 7
-5 -5
4 -7 3
7 -7
7 0
5 -1
-2 -2 2
5 -4
-3 -3
-9 2
-9 -1 8
-8 -9
-7 -4
-4 1
-5 9 4
-10 7
-2 6
-10 -8
3 -6 9
9 -5
-2 -9
-5 -1
8 -10 4
9 -4
-1 -2
0 -5
-1 6 1
8 -9
4 -6
-9 -2
6 -4 9
7 7
-1 7
-10 1
-3 3 9
2 -8
-2 5
-7 -10
-7 3 1
-8 -7
-3 9
-8 7
-1 5 3
-2 2
7 9
-3 -1
-7 1 2
-1 -8
-7 -3
9 -9
9 -3 1
9 5
5 -3
7 3
3 8 5
7 -10
-9 7
-10 7
-6 9 5
-2 4
-2 -2
3 -2
-5 -8 3
9 7
-4 -10
6 5
4 -9 2
-6 9
-10 -4
-8 -9
7 4 3
9 9
-9 -4
-2 -5
0 2 6
8 -6
9 -5
2 1
4 1 9
0 2
-2 9
-3 3
-8 -9 3
-4 -10
3 -9
7 7
7 -4 7
6 4
-1 4
-4 8
4 3 7
-3 4
-9 1
6 -1
-1 2 3
-5 -2
6 -1
3 8
-3 -4 7
6 9
-10 -3
2 -2
4 -9 2
-3 2
-2 8
-8 -10
-6 1 8
7 4
2 2
1 0
-5 7 6
1 -10
6 -2
-9 -3

 

输出

Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No

 

test4

60
9 14 14
-13 5
-11 -15
-5 -5
5 8 14
-14 7
-10 -6
-9 -1
2 -1 2
-15 -2
-9 8
1 2
-10 9 2
-7 -12
3 2
11 -14
-14 10 11
-10 11
-6 9
-3 13
0 -15 8
2 3
11 2
-15 -11
-12 12 11
-14 10
-4 4
-15 -14
-3 -1 8
0 -6
7 -8
6 -12
12 14 3
5 -6
-12 -6
-10 7
-14 -13 5
13 -9
-10 13
6 2
9 -12 2
-15 6
0 -15
5 -3
9 -12 14
-2 9
-6 -12
-9 -8
-7 -2 7
5 11
12 5
-14 8
7 -6 9
9 -6
5 9
10 -1
8 12 2
0 3
-8 14
3 12
-6 -8 7
0 14
10 -5
-3 13
10 6 13
12 7
-8 9
5 -12
-13 -9 5
14 -10
-9 -5
7 -15
-8 14 6
-15 -3
2 2
-15 -7
10 8 5
2 4
-10 -14
13 -4
11 10 2
-2 14
11 -12
-9 13
-9 -4 8
1 -15
-15 -3
6 13
0 -1 13
7 11
-5 -15
-5 -7
5 3 14
11 -1
-8 -15
13 -14
-7 3 1
-6 -5
12 7
-12 -12
7 -14 14
-10 -9
-15 14
-7 -2
-13 3 3
-11 5
-7 -14
-15 10
0 -10 6
-7 -8
-8 7
6 -10
-2 0 2
7 -3
-13 -5
-14 8
-4 3 10
-12 -7
10 -11
-8 6
-5 -3 9
-4 4
11 -7
7 -9
2 -2 6
9 7
-2 10
11 -15
-5 14 9
8 0
-8 10
-5 6
2 -5 3
-6 5
13 7
-15 -4
12 2 9
12 9
-5 -13
-6 -11
8 0 7
10 3
1 -7
-6 0
6 -12 1
13 10
-4 7
-2 -1
-13 5 12
-13 1
14 -14
-7 9
-2 -2 3
9 11
13 -14
4 -7
5 3 7
6 6
-15 6
-10 -7
-14 8 14
14 10
9 -11
14 -10
-12 -3 4
7 5
-15 7
-10 6
-8 -15 14
-10 -13
-2 -2
1 4
-2 5 13
-10 8
-15 6
-2 -5
-1 8 8
-1 -10
-13 -2
-15 -7
-2 4 6
7 1
-6 14
-8 12
-3 -15 12
-1 -15
1 -12
9 2
-8 -6 9
-4 -12
14 -9
-11 -4
13 -3 14
-10 -9
-7 -15
4 9
14 11 12
3 8
6 -15
-5 -1
-3 -7 3
-5 -15
-8 -2
8 -4
13 11 7
13 7
-14 12
-6 -9
-1 -5 13
2 12
8 -14
4 -3
-5 5 1
-14 4
-1 -15
11 -9
13 11 5
6 6
11 -11
-11 0
3 8 6
-8 -4
-14 11
7 -13
1 -4 2
-6 -4
-2 -2
5 -4
3 13 3
4 1
-3 -11
12 12
-15 6 1
9 -10
-10 3
-5 -5
-10 -14 11
-6 -15
8 -8
-5 -2

 

输出

No
No
No
No
Yes
No
Yes
Yes
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
Yes
No
No
Yes