用幾何模板,求外接圓,再判斷點在不在圓內
#include#include #include const double esp = 1e-9; //點 struct Point { double x, y; Point() {} Point(double x, double y) { this->x = x; this->y = y; } void read() { scanf(%lf%lf, &x, &y); } }; //線段 struct Line { Point p[2]; double A, B, C; Line() {} Line(Point a, Point b) { this->p[0] = a; this->p[1] = b; A = p[0].y - p[1].y; B = p[1].x - p[0].x; C = -(A * p[0].x + B * p[0].y); } }; //圓 struct Circle { Point center; double r; Circle() {} Circle(Point center, double r) { this->center = center; this->r = r; } }; //三角形 struct Tra { Point p[3]; Tra() {} Tra(Point a, Point b, Point c) { this->p[0] = a; this->p[1] = b; this->p[2] = c; } }; //點點距離 double dis(Point a, Point b) { double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } //點線對稱點 Point P_dc(Line l, Point p) { Point ans; ans.x = p.x - (2 * l.A * (l.A * p.x + l.B * p.y + l.C)) / (l.A * l.A + l.B * l.B); ans.y = p.y - (2 * l.B * (l.A * p.x + l.B * p.y + l.C)) / (l.A * l.A + l.B * l.B); return ans; } //三角形面積 double Tra_Area(Tra t) { return fabs((t.p[1].x - t.p[0].x) * (t.p[2].y - t.p[0].y) - (t.p[2].x - t.p[0].x) * (t.p[1].y - t.p[0].y)) / 2.0; } //求三角形外接圓 Circle Tra_Cir(Tra t) { Circle ans; double a = dis(t.p[0], t.p[1]); double b = dis(t.p[1], t.p[2]); double c = dis(t.p[2], t.p[0]); ans.r = (a * b * c) / (Tra_Area(t) * 4.0); double xA = t.p[0].x; double yA = t.p[0].y; double xB = t.p[1].x; double yB = t.p[1].y; double xC = t.p[2].x; double yC = t.p[2].y; double c1 = (xA*xA+yA*yA - xB*xB-yB*yB) / 2; double c2 = (xA*xA+yA*yA - xC*xC-yC*yC) / 2; ans.center.x = (c1*(yA - yC)-c2*(yA - yB)) / ((xA - xB)*(yA - yC)-(xA - xC)*(yA - yB)); ans.center.y = (c1*(xA - xC)-c2*(xA - xB)) / ((yA - yB)*(xA - xC)-(yA - yC)*(xA - xB)); return ans; } //判斷點在圓內(含邊界) bool In_Cir(Circle c, Point p) { double d = dis(p, c.center); if (d - c.r > esp) return false; return true; } int t; Point p[4]; bool judge(Circle pc) { if (!In_Cir(pc, p[3])) return true; Circle pc1 = Circle(P_dc(Line(p[0], p[1]), p[3]), pc.r); if (In_Cir(pc1, p[2]) && !In_Cir(pc1, p[3])) return true; pc1 = Circle(P_dc(Line(p[1], p[2]), p[3]), pc.r); if (In_Cir(pc1, p[0]) && !In_Cir(pc1, p[3])) return true; pc1 = Circle(P_dc(Line(p[0], p[2]), p[3]), pc.r); if (In_Cir(pc1, p[1]) && !In_Cir(pc1, p[3])) return true; return false; } int main() { int cas = 0; scanf(%d, &t); while (t--) { for (int i = 0; i < 4; i++) p[i].read(); Tra pt = Tra(p[0], p[1], p[2]); Circle pc = Tra_Cir(pt); printf(Case #%d: , ++cas); if (judge(pc)) printf(Safe ); else printf(Danger ); } return 0; }