首页 > 代码库 > [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 圆与三角形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。