模拟退火算法。

随机MAX个点,然后,退火移动,选取距离所有点中最短中最长者即可。理解和我上一篇一样。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
using namespace std;
const int MAXN=1010;
const int MAX=50;
const double inf=1e10;
const double eps=1e-3; struct point {
double x,y;
};
point p[MAXN]; point tar[MAX];
double best[MAXN];
int n; double ans_dis; point s,tp; double tmp_dis;
double X,Y; double getdouble(){
double ret=((rand()*rand())%1000000)*1.0/1e6;
return ret;
}
double dist(point &u,point &v){
return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
} double work(point &t){
double ret=inf;
for(int i=0;i<n;i++){
double tmp=dist(t,p[i]);
ret=min(ret,tmp);
}
return ret;
} int main(){
int cas; bool flag;
scanf("%d",&cas);
srand(time(0));
while(cas--){
scanf("%lf%lf%d",&X,&Y,&n);
for(int i=0;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(int i=0;i<MAX;i++){
tar[i].x=getdouble()*X;
tar[i].y=getdouble()*Y;
best[i]=work(tar[i]);
}
double T=100;
for(double t=T;t>eps;t*=0.8){
for(int i=0;i<MAX;i++){
for(int j=0;j<30;j++){
double tmp=getdouble();
if(rand()&1) tmp*=-1;
tp.x=tar[i].x+tmp*t;
tmp=getdouble();
if(rand()&1) tmp*=-1;
tp.y=tar[i].y+tmp*t;
if(tp.y>=0&&tp.y<Y&&tp.x>=0&&tp.x<=X){
double f=work(tp);
if(f>best[i]) {
tar[i]=tp; best[i]=f;
}
}
}
}
}
ans_dis=best[0];
for(int i=0;i<MAX;i++){
double fe=best[i];
if(fe>ans_dis){
s=tar[i];
ans_dis=fe;
}
}
printf("The safest point is (%.1lf, %.1lf).\n",s.x,s.y);
}
return 0;
}

  

最新文章

  1. SQL用法操作合集
  2. js--找字符串中出现最多的字符
  3. 反人类的java
  4. C语言出错问题汇总【需要更新】
  5. testng依赖,顺序,跳过
  6. 使用dynamic动态设置属性值与反射设置属性值性能对比
  7. quartznet笔记
  8. 使用sed,awk将love转换成LOVE,将CHINA转换成china
  9. C++疑难杂症
  10. 学习java 第1天
  11. tool
  12. BZOJ1984: 月下“毛景树”
  13. HTML5图片预览
  14. QML开源游戏
  15. DDD理论学习系列(12)-- 仓储
  16. ueditor单独调用上传附件和图片的功能
  17. [luogu4005]小Y和地铁【搜索+树状数组】
  18. keras的LSTM函数详解
  19. 使用Fiddler查看APP的请求接口、接口参数和返回值的方法
  20. 记录一次读取memcache缓存的优化

热门文章

  1. c programs
  2. Appium + python - swipe滑屏操作实例
  3. 利用poi,jxl将Excel数据导入数据库
  4. Django:提交表单报错:RuntimeError: You called this URL via POST, but the URL doesn’t end in a slash and you have A
  5. 管理mysql数据严格模式,和安全模式处理
  6. windows server 2012 r2 安装无法找到install.wim 错误代码0x80070026,以及制作U启动盘决解ISO文件超过5G大小限制的解决方案(转)
  7. ROS和OpenCV的对接cv_bridge
  8. SpringBoot入门系列(转)
  9. 11.03 在外链接中用OR逻辑
  10. spring boot注解