首页 > 代码库 > hdu4720Naive and Silly Muggles

hdu4720Naive and Silly Muggles

链接

一直理解的最小覆盖圆就是外接圆。。原来还要分钝角和锐角。。。

钝角的话就为最长边的中点,对于这题分别枚举一下外接圆以及中点的圆,判一下是不是在园外。

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 100000 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct Point 18 { 19     double x,y; 20     Point (double x=0,double y =0):x(x),y(y){} 21 }p[4]; 22 struct Circle 23 { 24     Point center; 25     double r; 26 }; 27 typedef Point pointt; 28 pointt operator - (Point a,Point b) 29 { 30     return Point(a.x-b.x,a.y-b.y); 31 } 32 int dcmp(double x) 33 { 34     if(fabs(x)<eps) return 0; 35     return x<0?-1:1; 36 } 37 double dis(Point a) 38 { 39     return a.x*a.x+a.y*a.y; 40 } 41 double cross(Point a,Point b) 42 { 43     return a.x*b.y-a.y*b.x; 44 } 45 double area() 46 { 47     return fabs(cross(p[1]-p[2],p[2]-p[3]))/2; 48 } 49 struct Circle Circumcircle() 50 { 51     Circle tmp; 52     double a,b,c,c1,c2; 53     double xa,ya,xb,yb,xc,yc; 54     a = sqrt(dis(p[3]-p[1])); 55     b = sqrt(dis(p[1]-p[2])); 56     c = sqrt(dis(p[2]-p[3])); 57     //¸ù¾Ýs = a*b*c/R/4£¬Çó°ë¾¶ 58     tmp.r = (a*b*c)/(area()*4.0); 59     xa = p[3].x; 60     ya = p[3].y; 61     xb = p[1].x; 62     yb = p[1].y; 63     xc = p[2].x; 64     yc = p[2].y; 65     c1 = (dis(p[3])-dis(p[1]))/2; 66     c2 = (dis(p[3])-dis(p[2]))/2; 67     tmp.center.x = (c1*(ya-yc)-c2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb)); 68     tmp.center.y = (c1*(xa-xc)-c2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb)); 69     return tmp; 70 } 71 int main() 72 { 73     int t,i; 74     cin>>t; 75     int kk = 0; 76     while(t--) 77     { 78         for(i = 1 ;i <= 3 ; i++) 79         scanf("%lf%lf",&p[i].x,&p[i].y); 80         Circle cc = Circumcircle(); 81         Point pp; 82         scanf("%lf%lf",&pp.x,&pp.y); 83         double r = cc.r; 84         r*=r; 85         printf("Case #%d: ",++kk); 86         if(dis(pp-cc.center)>r) 87         { 88             puts("Safe"); 89             continue; 90         } 91         r = dis(p[1]-p[2])/4; 92         cc.center.x = (p[1].x+p[2].x)/2; 93         cc.center.y = (p[1].y+p[2].y)/2; 94         if(dcmp(dis(p[3]-cc.center)-r)<=0&&dcmp(dis(pp-cc.center)-r)>0) 95         { 96             puts("Safe"); 97             continue; 98         } 99         r = dis(p[1]-p[3])/4;100         cc.center.x = (p[1].x+p[3].x)/2;101         cc.center.y = (p[1].y+p[3].y)/2;102         if(dcmp(dis(p[2]-cc.center)-r)<=0&&dcmp(dis(pp-cc.center)-r)>0)103         {104             puts("Safe");105             continue;106         }107         r = dis(p[3]-p[2])/4;108         cc.center.x = (p[3].x+p[2].x)/2;109         cc.center.y = (p[3].y+p[2].y)/2;110         if(dcmp(dis(p[1]-cc.center)-r)<=0&&dcmp(dis(pp-cc.center)-r)>0)111         {112             puts("Safe");113             continue;114         }115         puts("Danger");116     }117     return 0;118 }
View Code