最小覆盖圆的模板；

1 #include
      
         2 #include
       
          3 #include
        
           4 struct Point  5 {  6     double x;  7     double y;  8 } pt[1005];  9 struct Traingle 10 { 11     struct Point p[3]; 12 }; 13 struct Circle 14 { 15     struct Point center; 16     double r; 17 } ans; 18 //计算两点距离 19 double Dis(struct Point p, struct Point q) 20 { 21     double dx=p.x-q.x; 22     double dy=p.y-q.y; 23     return sqrt(dx*dx+dy*dy); 24 } 25 //计算三角形面积 26 double Area(struct Traingle ct) 27 { 28     return 29         fabs((ct.p[1].x-ct.p[0].x)*(ct.p[2].y-ct.p[0].y)-(ct.p[2].x-ct.p[0].x)*(ct.p[1].y-ct.p[0].y))/2.0; 30 } 31 //求三角形的外接圆，返回圆心和半径(存在结构体"圆"中) 32 struct Circle CircumCircle(struct Traingle t) 33 { 34     struct Circle tmp; 35     double a, b, c, c1, c2; 36     double xA, yA, xB, yB, xC, yC; 37     a = Dis(t.p[0], t.p[1]); 38     b = Dis(t.p[1], t.p[2]); 39     c = Dis(t.p[2], t.p[0]); 40 //根据S = a * b * c / R / 4;求半径R 41     tmp.r = (a*b*c)/(Area(t)*4.0); 42     xA = t.p[0].x; 43     yA = t.p[0].y; 44     xB = t.p[1].x; 45     yB = t.p[1].y; 46     xC = t.p[2].x; 47     yC = t.p[2].y; 48     c1 = (xA*xA+yA*yA - xB*xB-yB*yB) / 2; 49     c2 = (xA*xA+yA*yA - xC*xC-yC*yC) / 2; 50     tmp.center.x = (c1*(yA - yC)-c2*(yA - yB)) / ((xA - xB)*(yA - yC)-(xA - xC)*(yA - yB)); 51     tmp.center.y = (c1*(xA - xC)-c2*(xA - xB)) / ((yA - yB)*(xA - xC)-(yA - yC)*(xA - xB)); 52     return tmp; 53 } 54 //确定最小包围圆 55 struct Circle MinCircle(int num, struct Traingle ct) 56 { 57     struct Circle ret; 58     if (num==0) ret.r = 0.0; 59     else if (num==1) 60     { 61         ret.center = ct.p[0]; 62         ret.r = 0.0; 63     } 64     else if (num==2) 65     { 66         ret.center.x = (ct.p[0].x+ct.p[1].x)/2.0; 67         ret.center.y = (ct.p[0].y+ct.p[1].y)/2.0; 68         ret.r = Dis(ct.p[0], ct.p[1])/2.0; 69     } 70     else if(num==3) ret = CircumCircle(ct); 71     return ret; 72 } 73 //递归实现增量算法 74 void Dfs(int x, int num, struct Traingle ct) 75 { 76     int i, j; 77     struct Point tmp; 78     ans = MinCircle(num, ct); 79     if (num==3) return; 80     for (i=1; i<=x; i++) 81         if (Dis(pt[i], ans.center)>ans.r) 82         { 83             ct.p[num]=pt[i]; 84             Dfs(i-1, num+1, ct); 85             tmp=pt[i]; 86             for (j=i; j>=2; j--) 87                 pt[j]=pt[j-1]; 88             pt[1]=tmp; 89         } 90 } 91 void Solve(int n) 92 { 93     struct Traingle ct; 94     Dfs(n, 0, ct); 95 } 96 int main (void) 97 { 98     int n, i,t; 99     int ca=1;100     scanf("%d",&t);101     while (t--)102     {103         for (i=1; i<=3; i++)104             scanf("%lf %lf", &pt[i].x, &pt[i].y);105         Solve(3);106         double xx,yy;107         scanf("%lf%lf",&xx,&yy);108         printf("Case #%d: ",ca++);109         if((xx-ans.center.x)*(xx-ans.center.x)+(yy-ans.center.y)*(yy-ans.center.y)<=(ans.r)*(ans.r))110             puts("Danger");111         else puts("Safe");112     }113     return 0;114 }