Naive and Silly Muggles （计算几何）

Naive and Silly Muggles

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 137 Accepted Submission(s): 94

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?

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 x_i and y_i (|x_i, y_i| <= 10), indicating the three wizards' positions. Then a single line with two numbers q_x and q_y (|q_x, q_y| <= 10), indicating the muggle's position.

Output

For test case X, output "Case #X: " first, then output "Danger" or "Safe".

Sample Input

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

题意：给三个顶点的坐标，求能覆盖该三个点的最小的圆，若最后输入的点的坐标在圆外输出“Safe”,否则输出“Danger”;

第一次做数学题目，开始只想到了外接圆，但没分三角形是什么情况，而且三角形外接圆的圆心和半径貌似不会求；于是乎，搜了一下三角形外接圆的圆心和半径求法。

但是题解里说要讨论三角形的形状，就按这个思路敲得，没想到就1A了。

思路：先把三边长求出来，若三点共线，则最小圆的半径是最长边的1/2，否则根据三边判断三角形的形状，并找出最长边记录最长边的端点；

1>若是直角三角形或钝角三角形，最小圆的半径是最长边的1/2，

2>若是锐角三角形，最小圆就是外接圆，找出外接圆的圆心，圆心到任意顶点的距离即为半径；

最后比较最小圆的半径和圆心到那点的距离；

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 struct node
  8 {
  9     double x,y;
 10 } point[5];
 11 double disA_B,disA_C,disB_C,Maxdis;//分别记录三边长和最长边
 12 int a,b;//记录最长边的两个端点
 13 double center_x,center_y;//最小圆的圆心坐标
 14 double d;//记录圆心到该点的距离，与半径比较；
 15 double radiu;//锐角三角形外接圆半径；
 16 
 17 void Distance()
 18 {
 19     disA_B = sqrt((point[0].x-point[1].x)*(point[0].x-point[1].x)+
 20                   (point[0].y-point[1].y)*(point[0].y-point[1].y));
 21     disA_C = sqrt((point[0].x-point[2].x)*(point[0].x-point[2].x)+
 22                   (point[0].y-point[2].y)*(point[0].y-point[2].y));
 23     disB_C = sqrt((point[2].x-point[1].x)*(point[2].x-point[1].x)+
 24                   (point[2].y-point[1].y)*(point[2].y-point[1].y));
 25 
 26     if(disA_B >= disA_C && disA_B >= disB_C)
 27     {
 28         Maxdis = disA_B;
 29         a = 0;
 30         b = 1;
 31     }
 32     if(disA_C >= disA_B && disA_C >= disB_C)
 33     {
 34         Maxdis = disA_C;
 35         a = 0;
 36         b = 2;
 37     }
 38     if(disB_C >= disA_B && disB_C >= disA_C)
 39     {
 40         Maxdis = disB_C;
 41         a = 1;
 42         b = 2;
 43     }
 44 
 45 }
 46 //计算圆心到顶点的距离
 47 double check(double x1,double y1,double x2,double y2)
 48 {
 49     double d;
 50     d = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 51     return d;
 52 }
 53 //判断三角形类型
 54 int judge(double r1, double r2,double r3)
 55 {
 56     double res;
 57     res = r1*r1+r2*r2-r3*r3;
 58     if(res <= 0)
 59         return true;//钝角或直角三角形
 60     else return false;//锐角三角形
 61 }
 62 
 63 int main()
 64 {
 65     int test;
 66     scanf("%d",&test);
 67     for(int t = 1; t <= test; t++)
 68     {
 69         for(int i = 0; i < 4; i++)
 70             scanf("%lf %lf",&point[i].x,&point[i].y);
 71 
 72         Distance();
 73 
 74         printf("Case #%d: ",t);
 75 
 76         //三点在一条直线上，圆心在最长边的1/2处；
 77         if(point[0].x==point[1].x && point[0].x==point[2].x)
 78         {
 79             center_x = (point[a].x+point[b].x)/2.0;
 80             center_y = point[a].y;
 81             d = check(center_x,center_y,point[3].x,point[3].y);
 82             //printf("圆心（%lf,%lf）,距离 = %lf,半径 = %lf
",center_x,center_y,d,Maxdis/2.0);
 83             if(d > Maxdis/2.0)
 84                 printf("Safe
");
 85             else printf("Danger
");
 86             //printf("在一条直线上
");
 87         }
 88         else if(point[0].y==point[1].y && point[0].y==point[2].y)
 89         {
 90             center_x = point[a].x;
 91             center_y = (point[a].y+point[b].y)/2.0;
 92             d = check(center_x,center_y,point[3].x,point[3].y);
 93             //printf("圆心（%lf,%lf）,距离 = %lf,半径 = %lf
",center_x,center_y,d,Maxdis/2.0);
 94             if(d > Maxdis/2.0)
 95                 printf("Safe
");
 96             else printf("Danger
");
 97             //printf("在一条直线上
");
 98         }
 99 
100         //钝角或直角三角形，圆心是最长边的1/2处，半径是最长边的一半；
101         else if(judge(disA_B,disA_C,disB_C) || judge(disA_B,disB_C,disA_C) || judge(disA_C,disB_C,disA_B))
102         {
103             center_x = (point[a].x+point[b].x)/2.0;
104             center_y = (point[a].y+point[b].y)/2.0;
105             d = check(center_x,center_y,point[3].x,point[3].y);
106             //printf("圆心（%lf,%lf）,距离 = %lf,半径 = %lf
",center_x,center_y,d,Maxdis/2.0);
107             if(d > Maxdis/2.0)
108                 printf("Safe
");
109             else printf("Danger
");
110             //printf("是直角或钝角
");
111         }
112 
113         //锐角三角形，圆心是外接圆的圆心；
114         else if(!judge(disA_B,disA_C,disB_C) && !judge(disA_B,disB_C,disA_C) && !judge(disA_C,disB_C,disA_B))
115         {
116             center_x = 0;
117             center_y = 0;
118             double x1  =  point[0].x;
119             double x2  =  point[1].x;
120             double x3  =  point[2].x;
121             double y1  =  point[0].y;
122             double y2  =  point[1].y;
123             double y3  =  point[2].y;
124 
125             center_x=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2*(x3-x1)*(y2-y1)-2*((x2-x1)*(y3-y1)));
126             center_y=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2*(y3-y1)*(x2-x1)-2*((y2-y1)*(x3-x1)));
127             radiu = sqrt((point[0].x-center_x)*(point[0].x-center_x)+(point[0].y-center_y)*(point[0].y-center_y));
128 
129             d = check(center_x,center_y,point[3].x,point[3].y);
130             //printf("圆心（%lf,%lf）,距离 = %lf,半径 = %lf
",center_x,center_y,d,radiu);
131             if(d > radiu)
132                 printf("Safe
");
133             else printf("Danger
");
134             //printf("是锐角
");
135 
136         }
137 
138     }
139     return 0;
140 }

View Code

三角形外接圆模板

 1 void  circle_center(point[3])  
 2 {  
 3            double  x1,x2,x3,y1,y2,y3;
 4            double  radiu;//外接圆半径  
 5            double  x  =  0;  
 6            double  y  =  0;  
 7 
 8            x1  =  point[0].x; 
 9            x2  =  point[1].x;  
10            x3  =  point[2].x;  
11            y1  =  point[0].y;  
12            y2  =  point[1].y;  
13            y3  =  point[2].y;  
14 
15            //圆心坐标（x,y）;
16            x=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2*(x3-x1)*(y2-y1)-2*((x2-x1)*(y3-y1)));  
17            y=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2*(y3-y1)*(x2-x1)-2*((y2-y1)*(x3-x1)));  
18            //半径
19            radiu  =  sqrt((point[0].x - x)*(point[0].x - x) + (point[0].y - y)*(point[0].y - y));  
20 }

View Code