题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4720
题目大意：给你四个点，用前三个点绘制一个最小的圆，而这三个点必须在圆上或者在圆内，判断最一个点如果在圆外则是安全的，否则是危险的。
解题思路：我是先借用了别人的模板求三个点组成的最小的圆的圆心以及半径，就列出了圆的标准方程，将第四个点代入其中，则即可以判断此点是否在圆上还是圆外。
AC代码：
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-;
const int len = ;
struct Point
{
double x,y;
} p[len];
struct Line
{
Point a,b;
};
int dbcmp(double n)
{
return n < -eps ? - : n > eps;
}
double dis(Point a, Point b)
{
return ((a.x-b.x) * ( a.x-b.x) + ( a.y-b.y) * ( a.y-b.y));
} //求两直线的交点
Point intersection(Line u,Line v)
{
Point ret=u.a;
double t=((u.a.x-v.a.x)*(v.b.y-v.a.y)-(u.a.y-v.a.y)*(v.b.x-v.a.x))
/((u.a.x-u.b.x)*(v.b.y-v.a.y)-(u.a.y-u.b.y)*(v.b.x-v.a.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return ret;
}
//三角形外接圆圆心(外心)
Point center(Point a,Point b,Point c)
{
Line u,v;
u.a.x=(a.x+b.x)/;
u.a.y=(a.y+b.y)/;
u.b.x=u.a.x+(u.a.y-a.y);
u.b.y=u.a.y-(u.a.x-a.x);
v.a.x=(a.x+c.x)/;
v.a.y=(a.y+c.y)/;
v.b.x=v.a.x+(v.a.y-a.y);
v.b.y=v.a.y-(v.a.x-a.x);
return intersection(u,v);
} void min_cir(Point * p, int n, Point & cir, double &r)
{
random_shuffle(p, p + n);
cir = p[];
r = ;
for(int i = ; i < n; ++i)
{
if(dbcmp(dis(p[i],cir) -r) <= )continue;
cir = p[i];
r = ;
for(int j =; j < i ; ++j)
{
if(dbcmp(dis(p[j], cir) -r) <= )continue;
cir.x = (p[i].x + p[j].x) /;
cir.y = (p[i].y + p[j].y) /;
r = dis( cir, p[j]);
for(int k =; k < j; ++k)
{
if(dbcmp( dis(p[k], cir) -r) <= ) continue;
cir = center(p[i], p[j], p[k]);
r = dis( cir, p[k]);
} }
}
}
int main()
{
int t;
scanf("%d",&t);
for(int ca=; ca<=t; ca++)
{
for (int i = ; i < ; ++i)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
}
Point cir;
double r,dd,ee;
scanf("%lf%lf",&dd,&ee);
min_cir(p, , cir, r);
double aa=cir.x,bb=cir.y,cc=r;
double z=(dd-aa)*(dd-aa)+(ee-bb)*(ee-bb); if(z-cc>eps) printf("Case #%d: Safe\n",ca);
else printf("Case #%d: Danger\n",ca);
//printf("%lf %lf %lf %lf\n", aa, bb, cc,z);
}
return ;
}