POJ 1379 模拟退火
2024-09-27 09:55:06
模拟退火算法,很久之前就写过一篇文章了。双倍经验题(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 ;
}
最新文章
- UWP 图片剪切旋转工具
- linux文件权限查看及修改(实用)
- python模块之configparser
- css书写规则总结
- C#调用ArcGIS REST服务
- MySQL命令行查询乱码解决方法:
- VB的try语句,异常处理
- C# 键盘钩子类
- JavaScript显示输出
- 关于类似(i++)+(++i)
- jquery结合highcharts插件显示实时数据动态曲线图
- Swift 项目中常用的第三方框架
- week2-结对编程【网页实现四则运算】
- ----------- Rootkit 核心技术之绕过 IopParseDevice() 调用源检测逻辑 ---------------
- django报错Manager isn&#39;t accessible via UserInfo instances
- linux仅修改文件夹权限 分别批量修改文件和文件夹权限
- Base64简单原理
- Python档案袋( Sys 与 Import 模块)
- 002.Oracle安装部署-ASM
- Coursera台大机器学习技法课程笔记05-Kernel Logistic Regression
热门文章
- GreenPlum 大数据平台--web监控
- (转)模块readline解析
- 解决dns服务器未找到问题 &;&;DNS解析服务器&;&;连接问题
- how to use Sqoop to import/ export data
- ClouderManger搭建大数据集群时ERROR 2003 (HY000): Can&#39;t connect to MySQL server on &#39;ubuntucmbigdata1&#39; (111)的问题解决(图文详解)
- 动态替换animator的研究
- python pickle命令执行与marshal 任意代码执行
- Shell脚本检测程序,如果挂了就重启程序
- sql server数据库打不开
- C# 自定义属性Attribute