模拟退火算法,很久之前就写过一篇文章了。双倍经验题(POJ 2420)

题意:

在一个矩形区域内,求一个点的距离到所有点的距离最短的那个,最大。

这个题意,很像二分定义,但是毫无思路,也不能暴力枚举,那就模拟退火。

参考著名的ACdream,哈哈,有个共同点,那就是,大部分的代码,都没有做接受准则,这也许是acmer对智能算法的不习惯吧~~~

#include <stdio.h>
#include <math.h>
#include <algorithm> using namespace std; const int maxn = ; int X,Y,M;
int Kase; struct Node {
double x,y;
}nodes[maxn]; int dx[] = {,,-,};
int dy[] = {-,,,}; double dist(Node a,Node b) {
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
} double calc(Node p) {
double ret = 0x3f3f3f3f;
for(int i = ; i < M; i++)
ret = min(ret,dist(p,nodes[i]));
return ret;
} int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&Kase);
while(Kase--) {
scanf("%d%d%d",&X,&Y,&M); for(int i = ; i < M; i++) scanf("%lf%lf",&nodes[i].x,&nodes[i].y); Node s;
s.x = X/;
s.y = Y/; double t = max(X,Y);
double ansx = X/;
double ansy = Y/;
double ans = calc(s); Node tmp;
tmp.x = ;
tmp.y = ;
double anstmp = calc(tmp);
if(anstmp>ans) {
ans = anstmp;
ansx = ;
ansy = ;
} tmp.x = ;
tmp.y = Y;
anstmp = calc(tmp);
if(anstmp>ans) {
ans = anstmp;
ansx = ;
ansy = Y;
} tmp.x = X;
tmp.y = ;
anstmp = calc(tmp);
if(anstmp>ans) {
ans = anstmp;
ansx = X;
ansy = ;
} tmp.x = X;
tmp.y = Y;
anstmp = calc(tmp);
if(anstmp>ans) {
ans = anstmp;
ansx = X;
ansy = Y;
} while(t>1e-) {
bool flag = true;
while(flag) {
flag = false;
for(int i = ; i < ; i++) {
Node v;
v.x = s.x + dx[i]*t;
v.y = s.y + dy[i]*t;
if(v.x>X||v.y>Y||v.x<||v.y<) continue; double tp = calc(v); if(tp>ans) {
ans = tp;
flag = true;
ansx = v.x;
ansy = v.y;
s = v;
}
}
}
t = t*0.98;
} printf("The safest point is (%.1f, %.1f).\n",ansx,ansy);
}
return ;
}

最新文章

  1. UWP 图片剪切旋转工具
  2. linux文件权限查看及修改(实用)
  3. python模块之configparser
  4. css书写规则总结
  5. C#调用ArcGIS REST服务
  6. MySQL命令行查询乱码解决方法:
  7. VB的try语句,异常处理
  8. C# 键盘钩子类
  9. JavaScript显示输出
  10. 关于类似(i++)+(++i)
  11. jquery结合highcharts插件显示实时数据动态曲线图
  12. Swift 项目中常用的第三方框架
  13. week2-结对编程【网页实现四则运算】
  14. ----------- Rootkit 核心技术之绕过 IopParseDevice() 调用源检测逻辑 ---------------
  15. django报错Manager isn&#39;t accessible via UserInfo instances
  16. linux仅修改文件夹权限 分别批量修改文件和文件夹权限
  17. Base64简单原理
  18. Python档案袋( Sys 与 Import 模块)
  19. 002.Oracle安装部署-ASM
  20. Coursera台大机器学习技法课程笔记05-Kernel Logistic Regression

热门文章

  1. GreenPlum 大数据平台--web监控
  2. (转)模块readline解析
  3. 解决dns服务器未找到问题 &amp;&amp;DNS解析服务器&amp;&amp;连接问题
  4. how to use Sqoop to import/ export data
  5. ClouderManger搭建大数据集群时ERROR 2003 (HY000): Can&#39;t connect to MySQL server on &#39;ubuntucmbigdata1&#39; (111)的问题解决(图文详解)
  6. 动态替换animator的研究
  7. python pickle命令执行与marshal 任意代码执行
  8. Shell脚本检测程序,如果挂了就重启程序
  9. sql server数据库打不开
  10. C# 自定义属性Attribute