题目链接: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 ;
}

最新文章

  1. ios外包公司—北京动点软件分享:IOS工程自动打包并发布脚本实现
  2. iOS获取文件和文件夹大小
  3. Don&#39;t Repeat Yourself (不要重复你自己)
  4. IntelliJ IDEA 使用教程 - AS3篇
  5. 去掉搜狗拼音烦人的x+;进入搜狗搜索
  6. Android实现弹出输入法时,顶部固定,中间部分上移的效果
  7. BZOJ 1048 分割矩阵
  8. Qt容器类的对象模型及应用(线性结构篇)(好多图,比较清楚)
  9. 让MySQL数据库支持Emoji表情
  10. 测试人员如何使用Git部署测试环境
  11. Docker 镜像仓库
  12. mysql的初次使用操作
  13. SQL partition by的用法
  14. python day 09 文件操作
  15. Zookeeper session超时
  16. Firebird reset SYSDBA password
  17. Arduino IDE 安装esp8266 2.4.rc2的编译环境
  18. LoadRunner 11简单使用
  19. 虚拟机中安装 centOS,本地安装 SSH 连接 - 01
  20. Java中基于HotSpot虚拟机的垃圾收集器

热门文章

  1. 从腾讯QQgame高性能服务器集群架构看&ldquo;分而治之&rdquo;与&ldquo;自治&rdquo;等分布式架构设计原则
  2. jstl的formatNumber标签的四舍五入问题
  3. 关于vs2008使用oracleclient链接oracle数据库报报错OCIEnvCreate 失败,返回代码为 -1,但错误消息文本不可用
  4. C#管理异常和错误
  5. new、delete用法(一)
  6. 分享一个自己写的基于TP的关系模型(2)
  7. hibernate一些方法
  8. Touch组件实现原理
  9. Safari浏览器的调试
  10. Android 开机过程PMS分析