1298 圆与三角形 
基准时间限制：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 5Output示例
Yes
No题解：
通过顶点和圆心的距离将三角形和圆关系分为三类：
1、部分顶点在圆内，此时必定相交；
2、全部顶点在圆内，此时必定不相交；
3、全部顶点在圆外，此时可能相交也可能不相交；
对于第3种情况，我们知道只有同时符合以下两种情况是圆与三角形相交
1、圆心到直线距离小于等于半径；d<=r;
2、对应边和两顶点与圆心连线夹角为锐角（此时和圆心相距最短点在线段上）;
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
double a,b,r;
struct node{
double x,y;
}p[4];
bool check()
{
double A,B,C,D,E,F;
for(int i=1;i<=3;i++)
for(int j=i+1;j<=3;j++){
A=p[j].y-p[i].y;
B=p[i].x-p[j].x;
C=p[j].x*p[i].y-p[i].x*p[j].y;
D=(A*a+B*b+C)*(A*a+B*b+C);
if(D<=(A*A+B*B)*r*r){//圆心到该直线的距离小于半径
E=(a-p[i].x)*(p[j].x-p[i].x)+(b-p[i].y)*(p[j].y-p[i].y);//向量相乘
F=(a-p[j].x)*(p[i].x-p[j].x)+(b-p[j].y)*(p[i].y-p[j].y);
if(E>0&&F>0)//两顶点对应夹角为锐角说明最小距离在两顶点之间
return 1;//找到相交边
}
}
return 0;
}
int main()
{
int T,cnt;
scanf("%d",&T);
while(T--)
{
cnt=0;//记录圆内三角形顶点个数
scanf("%lf%lf%lf",&a,&b,&r);
for(int i=1;i<=3;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);//输入三个顶点
if((p[i].x-a)*(p[i].x-a)+(p[i].y-b)*(p[i].y-b)<=r*r)//判断该点是否在圆内
cnt++;
}
if(cnt>0&&cnt<3)//圆内有顶点但不包括全部则必相交
printf("Yes\n");
else if(cnt==3||!check())//三角形全部在内部或者全部在外面无相交边
printf("No\n");
else
printf("Yes\n");
}
return 0;
}