首页 > 代码库 > HDU 4720 :Naive and Silly Muggles
HDU 4720 :Naive and Silly Muggles
题目:HDU 4720 :Naive and Silly Muggles
题目大意:这题的意思是给出三个点, 然后在给出另一个点,问这个点会不会在覆盖前面三个点的最小的圆里面(包括边界), 在里面最输出danger, 如果任何情况下这个点都不在圆里面,那么就输出safe。
解题思路:三个点最小的覆盖的圆是三角形的外接圆,这样的圆面积一定是最小的。 但是相同面积的圆,所在的位置,覆盖的点会是不一样的。例如垂心关于三条边的对称点,以某个对称点为圆心的圆用之前的半径做圆,如果能够覆盖原来的三个点(点可能在内部也可能在边界),这样的圆也是可以的,这样的圆和之前的圆位置就不一样了, 所覆盖的点也是不一样的。
代码:
#include <stdio.h> #include <math.h> const double esp = 1e-9; struct POINT { double x, y; }point[4], center; struct LINE { double a, b, c; }; LINE getline (POINT p1, POINT p2) { LINE l; l.a = (p2.y - p1.y); l.b = (p1.x - p2.x); l.c = p1.x * p2.y - p2.x * p1.y; return l; } //两条直线的交点 POINT inter_point (LINE l1, LINE l2) { POINT p; p.y = (l2.a * l1.c - l1.a * l2.c) / (l2.b * l1.a - l2.a * l1.b); p.x = (l1.c * l2.b - l2.c * l1.b) / (l2.a * l1.b - l2.b * l1.a); return p; } //外界圆的圆心 POINT circle_p (POINT p1, POINT p2, POINT p3 ) { POINT p; double a = p2.x - p1.x; double b = p2.y - p1.y; double c = p2.y * p2.y - p1.y * p1.y + p2.x * p2.x - p1.x * p1.x; double d = p3.x - p1.x; double e = p3.y - p1.y; double f = p3.y * p3.y - p1.y * p1.y + p3.x * p3.x - p1.x * p1.x; p.y = (f * a - c * d) / (e * a - b * d) * 0.5; p.x = (c - 2 * p.y * b) / (2 * a); return p; } double dis (POINT p1, POINT p2) { double dx = p1.x - p2.x; double dy = p1.y - p2.y; return sqrt (pow (dx, 2) + pow (dy, 2)); } bool solve () { double r = dis (center , point[0]); if (dis (center , point[3]) - r > esp) return false; LINE l1, l2; POINT p; int t; for (int i = 0; i < 3; i++) { t = (i + 2) % 3; l1 = getline (point[i], point[( i + 1 ) % 3]); l2.a = l1.b; l2.b = -l1.a; l2.c = l1.a * center.y - l1.b * center.x; p = inter_point (l1, l2); p.x = (p.x * 2 - center.x); p.y = (p.y * 2 - center.y); if (dis (p, point[t]) - r > esp) continue; if (dis (p, point[3]) - r > esp) return false; } return true; } int main () { int t; double x, y; scanf ("%d", &t); for (int i = 1; i <= t; i++) { for (int j = 0; j < 4; j++) { scanf ("%lf%lf", &x, &y); point[j].x = x; point[j].y = y; } center = circle_p(point[0], point[1], point[2]); printf ("Case #%d: %s\n", i, solve()?"Danger":"Safe"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。