Problem Description
Three wizards are doing a experiment. To avoid from bothering, a special magic is set around them. The magic forms a circle, which covers those three wizards, in other words, all of them are inside or on the border of the circle. And due to save the magic power, circle's area should as smaller as it could be.
Naive and silly "muggles"(who have no talents in magic) should absolutely not get into the circle, nor even on its border, or they will be in danger.
Given the position of a muggle, is he safe, or in serious danger?
Naive and silly "muggles"(who have no talents in magic) should absolutely not get into the circle, nor even on its border, or they will be in danger.
Given the position of a muggle, is he safe, or in serious danger?
Input
The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case there are four lines. Three lines come each with two integers xi and yi (|xi, yi| <= 10), indicating the three wizards' positions. Then a single line with two numbers qx and qy (|qx, qy| <= 10), indicating the muggle's position.
For each test case there are four lines. Three lines come each with two integers xi and yi (|xi, yi| <= 10), indicating the three wizards' positions. Then a single line with two numbers qx and qy (|qx, qy| <= 10), indicating the muggle's position.
Output
For test case X, output "Case #X: " first, then output "Danger" or "Safe".
Sample Input
3
0 0
2 0
1 2
1 -0.5
0 0
2 0
1 2
1 -0.6
0 0
3 0
1 1
1 -1.5
Sample Output
Case #1: Danger
Case #2: Safe
Case #3: Safe
Source
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #define exd 1e-6 7 using namespace std; 8 struct node 9 { 10 int x,y; 11 }; 12 struct NN 13 { 14 double x,y; 15 }; 16 struct MM 17 { 18 double x1,y1,len; 19 double x2,y2; 20 }; 21 node p[3]; 22 double x,y; 23 double Radius; 24 MM dd[3]; 25 NN center; 26 double dis() 27 { 28 return sqrt((x-center.x)*(x-center.x)+(y-center.y)*(y-center.y)); 29 } 30 double dist2(node a,node b) 31 { 32 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 33 } 34 35 double dist1(NN a,node b) 36 { 37 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 38 } 39 40 bool cmp(MM a,MM b) 41 { 42 return a.len>b.len; 43 } 44 45 int judge() 46 { 47 if(dd[2].len*dd[2].len+dd[1].len*dd[1].len>dd[0].len*dd[0].len) 48 return 1; 49 else 50 return 2; 51 } 52 void miniCircle() 53 { 54 double Xmove=p[0].x; 55 double Ymove=p[0].y; 56 p[1].x=p[1].x-p[0].x; 57 p[1].y=p[1].y-p[0].y; 58 p[2].x=p[2].x-p[0].x; 59 p[2].y=p[2].y-p[0].y; 60 p[0].x=0; 61 p[0].y=0; 62 double x1=p[1].x,y1=p[1].y,x2=p[2].x,y2=p[2].y; 63 double m=2.0*(x1*y2-y1*x2); 64 65 center.x=(x1*x1*y2-x2*x2*y1+y1*y2*(y1-y2))/m; 66 center.y=(x1*x2*(x2-x1)-y1*y1*x2+x1*y2*y2)/m; 67 Radius=dist1(center,p[0]); 68 center.x+=Xmove; 69 center.y+=Ymove; 70 } 71 int main() 72 { 73 int t; 74 int cas=1; 75 scanf("%d",&t); 76 while(t--) 77 { 78 for(int i=0;i<3;i++) 79 { 80 scanf("%d%d",&p[i].x,&p[i].y); 81 } 82 scanf("%lf%lf",&x,&y); 83 dd[0].x1=p[0].x,dd[0].y1=p[0].y; 84 dd[0].x2=p[1].x,dd[0].y2=p[1].y; 85 dd[0].len=dist2(p[0],p[1]); 86 dd[1].x1=p[0].x,dd[1].y1=p[0].y; 87 dd[1].x2=p[2].x,dd[1].y2=p[2].y; 88 dd[1].len=dist2(p[0],p[2]); 89 dd[2].x1=p[1].x,dd[2].y1=p[1].y; 90 dd[2].x2=p[2].x,dd[2].y2=p[2].y; 91 dd[2].len=dist2(p[1],p[2]); 92 sort(dd,dd+3,cmp); 93 if(judge()==2) 94 { 95 Radius=dd[0].len/2.0; 96 center.x=(dd[0].x1+dd[0].x2)/2.0; 97 center.y=(dd[0].y1+dd[0].y2)/2.0; 98 } 99 else 100 { 101 miniCircle(); 102 } 103 double ans=dis(); 104 if(ans<Radius) 105 { 106 printf("Case #%d: Danger ",cas++); 107 } 108 else if(fabs(ans-Radius)<exd) 109 { 110 printf("Case #%d: Danger ",cas++); 111 } 112 else 113 { 114 printf("Case #%d: Safe ",cas++); 115 } 116 } 117 return 0; 118 }
此题属于计算几何；
根据给出的三个点形成一个尽量小的圆使得这三个点在这个圆的里面或者边缘上，然后判断第四个点是否在这个形成的圆的里面或者边缘上；
解题思路：
首先确定这三个点能否构成一个三角形或者一个钝角三角形，如果满足条件，则说明形成的那个圆的半径肯定是前面三个点中最远距离的两个点，圆也就是那两个点的中点作为圆心，然后判断第四个点到圆心的距离与半径进行比较；
如果不满足条件，也就是这三个点形成的是锐角三角形或者直角三角形，那么圆心与半径的确定就是求三角形外心的算法，能够确定圆心以及半径，然后进行判断