Naive and Silly Muggles
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 616 Accepted Submission(s): 395
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 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
2013 ACM/ICPC Asia Regional Online —— Warmup2
//几何问题
//题意，给你四个点，看看给定的最后一个点在不在另外三个点组成的最小的圆内，在就是Danger，不在就是Safe
思路：找出圆心，看给定点到圆心的距离就知道该点在不在圆内
有两种情况：
1.三个点均在圆上
2.有一个点在圆内
三点在圆上的情况，可以利用ABC三点组成两条线，分别求两条线的中垂线，中垂线的交点即为圆心，进而求半径
三点有一点在圆内的情况，先确定圆心（其中一条线的重中点），还要保证另外一点与圆心的距离一点小于半径，才能拿去和上面求得半径作比较。
一旦发现有更小的半径就要更新
AC代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
struct node
{
double x,y;
}a[5];
int main()
{
int i,j,n,m=1,flag1,flag2;
double xx,yy,x1,y1,x2,y2,x,y,r,len,k1,k2,b1,b2;
scanf("%d",&n);
while(n--)
{
memset(a,0,sizeof(a));
flag1=0;flag2=0;
for(i=0;i<3;i++)
scanf("%lf %lf",&a[i].x,&a[i].y);
scanf("%lf %lf",&xx,&yy);
//求出直线AB的中垂线的方程y=k1*x+b1
x1=(a[1].x+a[0].x)/2;
y1=(a[1].y+a[0].y)/2;
if(a[1].y-a[0].y!=0)//判断斜率是否存在
{
k1=-1*(a[1].x-a[0].x)/(a[1].y-a[0].y);//斜率
b1=y1-k1*x1;//y=k*x+b中的常数b
}
else//这是斜率不存在的情况
{
x=x1;//直接得到圆心横坐标
flag1=1;
}
//求出直线BC的中垂线的方程y=k2*x+b2
x2=(a[2].x+a[1].x)/2;
y2=(a[2].y+a[1].y)/2;
if(a[2].y-a[1].y!=0)//判断斜率是否存在
{
k2=-1*(a[2].x-a[1].x)/(a[2].y-a[1].y);
b2=y2-k2*x2;
}
else//这是斜率不存在的情况
{
x=x2;//直接得到圆心横坐标
flag2=1;
}
if(flag1!=1&&flag2!=1)//两个中垂线的交点即为圆心
{
//两个中垂线的方程联立求解，得出圆心
x=(b2-b1)/(k1-k2);
y=x*k1+b1;
}
else
{
if(flag1==1)//如果之前有个边没有斜率（相当于已知圆心横坐标，只要带入另一个垂线的方程即可）
{
y=x*k2+b2;
}
else
{
y=x*k1+b1;
}
}
//printf("第一次：x=%.2lf y=%.2lf\n",x,y);//(x,y)即为圆心坐标
r=sqrt((x-a[0].x)*(x-a[0].x)+(y-a[0].y)*(y-a[0].y));//半径
//printf("第一次：r=%.2lf\n",r);
//上面是三个点均在圆上的情况，下面是一个点在园内的情况，为的是求出最短半径
double rx,p1,p2,r1,r2,r3,min=999999,px,py;
p1=(a[1].x+a[0].x)/2;
p2=(a[1].y+a[0].y)/2;
rx=sqrt((a[1].x-p1)*(a[1].x-p1)+(a[1].y-p2)*(a[1].y-p2));
r1=sqrt((a[2].x-p1)*(a[2].x-p1)+(a[2].y-p2)*(a[2].y-p2));
//printf("p1=%.2lf p2=%.2lf\n",p1,p2);
if(rx<min&&r1<=rx)
{
min=rx;
px=p1;
py=p2;
}
p1=(a[1].x+a[2].x)/2;
p2=(a[1].y+a[2].y)/2;
rx=sqrt((a[1].x-p1)*(a[1].x-p1)+(a[1].y-p2)*(a[1].y-p2));
r2=sqrt((a[0].x-p1)*(a[0].x-p1)+(a[0].y-p2)*(a[0].y-p2));
//printf("p1=%.2lf p2=%.2lf\n",p1,p2);
if(rx<min&&r2<=rx)
{
min=rx;
px=p1;
py=p2;
}
p1=(a[2].x+a[0].x)/2;
p2=(a[2].y+a[0].y)/2;
rx=sqrt((a[2].x-p1)*(a[2].x-p1)+(a[2].y-p2)*(a[2].y-p2));
r3=sqrt((a[1].x-p1)*(a[1].x-p1)+(a[1].y-p2)*(a[1].y-p2));
//printf("p1=%.2lf p2=%.2lf\n",p1,p2);
if(rx<min&&r3<=rx)
{
min=rx;
px=p1;
py=p2;
}
if(r>min)//比较出最小半径，并记录圆心
{
r=min;
x=px;
y=py;
}
//printf("第二次：x=%.2lf y=%.2lf\n",x,y);
len=sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));//计算要求的点到圆心的距离
//printf("第二次：r=%.2lf\n",r);
//printf("len=%.2lf\n",len);
if(len<=r)
{
printf("Case #%d: Danger\n",m++);
}
else
printf("Case #%d: Safe\n",m++);
}
return 0;
}