首页 > 代码库 > [51nod]1298 圆与三角形

[51nod]1298 圆与三角形

1298 圆与三角形
题目来源: HackerRank
给出圆的圆心和半径,以及三角形的三个顶点,问圆同三角形是否相交。相交输出"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

要点:
  关键是判断圆与三角形是否相交,相交有多种情况:顶点在圆上,至少一个顶点在圆内至少一个在圆外,顶点都在圆外但是有边在圆的内部,相切的情况等,所以选择判断不相交的情况。
只有两种:三个顶点都在圆内或者圆心到三条边的距离都大于半径。其余的就是相交的情况。

代码:
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

const double eps = 1e-8;
int cmp(double x)
{
    if (fabs(x) < eps) return 0;
    if (x > 0) return 1;
    return -1;
}

struct point
{
    double x, y;

    point() {}
    point(double a, double b):x(a),y(b) {}

    void input() {
        scanf("%lf%lf", &x, &y);
    }
    friend point operator - (const point &a, const point &b) {
        return point(a.x-b.x, a.y-b.y);
    }
    double norm() {
        return sqrt(x*x + y*y);
    }
};

struct cicle
{
    point p;
    double r;

    void input() {
        scanf("%lf%lf%lf", &p.x, &p.y, &r);
    }
};

double dot(const point &a, const point &b) 
{
    return a.x*b.x + a.y*b.y;
}

double det(const point &a, const point &b)
{
    return a.x*b.y - a.y*b.x;
}

double dist(const point &a, const point &b)
{
    return (a-b).norm();
}

double dis_point_segment(const point p, const point s, const point t)
{
    if (cmp(dot(p-s,t-s))<0) return (p-s).norm();
    if (cmp(dot(p-t,s-t))<0) return (p-t).norm();
    return fabs(det(s-p,t-p)/dist(s, t));
}

bool cross(cicle o, point a, point b, point c)
{
    double d1, d2, d3;
    d1 = dist(o.p, a);
    d2 = dist(o.p, b);
    d3 = dist(o.p, c);

    if (d1<o.r && d2<o.r && d3<o.r)
        return false;
    if (dis_point_segment(o.p, a, b)>o.r
        && dis_point_segment(o.p, a, c)>o.r
        && dis_point_segment(o.p, b, c)>o.r)
        return false;
    return true;
}

int main()
{
    //freopen("1.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        cicle o;
        o.input();
        point a, b, c;
        a.input();
        b.input();
        c.input();
        if (cross(o, a, b, c))
            printf("Yes\n");
        else
            printf("No\n");

    }

    return 0;
}

 

[51nod]1298 圆与三角形