51Nod 1298 圆与三角形

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 using namespace std;
  5 
  6 const double eps = 1e-8;
  7 int cmp(double x)
  8 {
  9     if (fabs(x) < eps) return 0;
 10     if (x > 0) return 1;
 11     return -1;
 12 }
 13 
 14 struct point
 15 {
 16     double x, y;
 17 
 18     point() {}
 19     point(double a, double b) :x(a), y(b) {}
 20 
 21     void input() {
 22         scanf("%lf%lf", &x, &y);
 23     }
 24     //重载操作符
 25     friend point operator - (const point &a, const point &b) {
 26         return point(a.x - b.x, a.y - b.y);
 27     }
 28 
 29     double norm() {
 30         return sqrt(x*x + y*y);
 31     }
 32 };
 33 
 34 struct cicle
 35 {
 36     point p;        //圆心
 37     double r;
 38 
 39     void input() {
 40         scanf("%lf%lf%lf", &p.x, &p.y, &r);
 41     }
 42 };
 43 
 44 double dot(const point &a, const point &b)
 45 {
 46     return a.x*b.x + a.y*b.y;
 47 }
 48 
 49 double det(const point &a, const point &b)
 50 {
 51     return a.x*b.y - a.y*b.x;
 52 }
 53 
 54 double dist(const point &a, const point &b)
 55 {
 56     return (a - b).norm();
 57 }
 58 
 59 double dis_point_segment(const point p, const point s, const point t)
 60 {
 61     if (cmp(dot(p - s, t - s))<0) return (p - s).norm();
 62     if (cmp(dot(p - t, s - t))<0) return (p - t).norm();
 63     return fabs(det(s - p, t - p) / dist(s, t));
 64 }
 65 
 66 bool cross(cicle o, point a, point b, point c)
 67 {
 68     double d1, d2, d3;
 69     d1 = dist(o.p, a);
 70     d2 = dist(o.p, b);
 71     d3 = dist(o.p, c);
 72     //各点到圆心的距离
 73     if (d1<o.r && d2<o.r && d3<o.r)
 74         //都在圆内
 75         return false;
 76     if (dis_point_segment(o.p, a, b)>o.r 
 77         && dis_point_segment(o.p, a, c)>o.r 
 78         && dis_point_segment(o.p, b, c)>o.r)
 79         return false;
 80     return true;
 81 }
 82 
 83 int main()
 84 {
 85     int T;
 86     scanf("%d", &T);
 87     while (T--) {
 88         cicle o;
 89         o.input();
 90         point a, b, c;
 91         a.input();
 92         b.input();
 93         c.input();
 94         if (cross(o, a, b, c))
 95             printf("Yes
");
 96         else
 97             printf("No
");
 98     }
 99     return 0;
100 }