HDU 4720 Naive and Silly Muggles 2013年四川省赛题
2024-10-13 11:33:57
题目链接: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 ;
}
最新文章
- ios外包公司—北京动点软件分享:IOS工程自动打包并发布脚本实现
- iOS获取文件和文件夹大小
- Don&#39;t Repeat Yourself (不要重复你自己)
- IntelliJ IDEA 使用教程 - AS3篇
- 去掉搜狗拼音烦人的x+;进入搜狗搜索
- Android实现弹出输入法时,顶部固定,中间部分上移的效果
- BZOJ 1048 分割矩阵
- Qt容器类的对象模型及应用(线性结构篇)(好多图,比较清楚)
- 让MySQL数据库支持Emoji表情
- 测试人员如何使用Git部署测试环境
- Docker 镜像仓库
- mysql的初次使用操作
- SQL partition by的用法
- python day 09 文件操作
- Zookeeper session超时
- Firebird reset SYSDBA password
- Arduino IDE 安装esp8266 2.4.rc2的编译环境
- LoadRunner 11简单使用
- 虚拟机中安装 centOS,本地安装 SSH 连接 - 01
- Java中基于HotSpot虚拟机的垃圾收集器
热门文章
- 从腾讯QQgame高性能服务器集群架构看&ldquo;分而治之&rdquo;与&ldquo;自治&rdquo;等分布式架构设计原则
- jstl的formatNumber标签的四舍五入问题
- 关于vs2008使用oracleclient链接oracle数据库报报错OCIEnvCreate 失败,返回代码为 -1,但错误消息文本不可用
- C#管理异常和错误
- new、delete用法(一)
- 分享一个自己写的基于TP的关系模型(2)
- hibernate一些方法
- Touch组件实现原理
- Safari浏览器的调试
- Android 开机过程PMS分析