给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出"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"。

输入样例

输出样例

Yes

No

题意是求圆与三角形是否相交，即是否有交点，实际上就是求圆心到三边的距离，不过 要注意这里的边是线段，可不是求到直线的距离，如果三个点都在圆内或者圆心到三条边的距离都大于半径，那么就是不相交，其他的情况相交，
点与点之间的距离很好求，点到线的距离可以借助海伦公式，海伦公式求出点与边两点组成三角形的面积，而面积又等于点到直线的距离*边长/2，以此能求出点到直线距离，还要另外分点到直线距离不等于点到线段距离的情况。
还有精度问题，全程用浮点数，判断相等的情况要用到精度，不然可能出错。
代码：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#define MAX 101

#define eps 1e-6

using namespace std;

typedef pair<double,double> pa;

int t;

double r;

pa cir,a,b,c;

double ptop(pa x,pa y) {///点到点

    return sqrt((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second));

}

double ptol(pa p,pa la,pa lb) {///点到线

    double x = ptop(p,la);

    double y = ptop(p,lb);

    double z = ptop(lb,la);

    if(x * x >= y * y + z * z) return y;///不能用点到直线

    if(y * y >= x * x + z * z) return x;///不能用点到直线

    double hc = (x + y + z) / ;

    return sqrt(hc * (hc - x) * (hc - y) * (hc - z)) *  / z;///点到直线

}

bool check(pa p,double rr,pa x,pa y,pa z) {

    if(ptop(cir,x) - rr < -eps && ptop(cir,y) - rr < -eps && ptop(cir,z) - rr < -eps

       || ptol(p,x,y) - rr > eps && ptol(p,z,y) - rr > eps && ptol(p,x,z) - rr > eps) return false;

    return true;

}

int main() {

    scanf("%d",&t);

    while(t --) {

        scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf",&cir.first,&cir.second,&r,&a.first,&a.second,&b.first,&b.second,&c.first,&c.second);

        if(check(cir,r,a,b,c)) puts("Yes");

        else puts("No");

    }

}

巴特西

51nod 1298 圆与三角形

输入

输出

输入样例

输出样例

最新文章

热门文章