POJ1379：Run Away
我对模拟退火的理解：https://www.cnblogs.com/AKMer/p/9580982.html
我对爬山的理解：https://www.cnblogs.com/AKMer/p/9555215.html
题目传送门：http://poj.org/problem?id=1379
题目意思是要求规定大小平面内某一点，该点到所有给定点的距离中最小距离最大。
类似于费马点做法……不过把统计距离和变成了求距离最小值最大。
费马点不会的可以先看看这篇博客。
BZOJ3680：吊打XXXhttps://www.cnblogs.com/AKMer/p/9588724.html
时间复杂度：\(O(能A)\)
空间复杂度：\(O(能A)\)
爬山算法代码如下：
#include
#include
#include
#include
using namespace std;#define sqr(a) ((a)*(a))int n,lenx,leny;
double ansx,ansy,ans;int read() {int x=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';return x*f;
}struct point {double x,y;
}p[1001];double len() {double x=rand()%200000-100000;return x/100000;
}double dis(double x1,double y1,double x2,double y2) {return sqrt(sqr(x1-x2)+sqr(y1-y2));
}double calc(double x,double y) {double tmp=1e18;for(int i=1;i<=n;i++)tmp=min(tmp,dis(x,y,p[i].x,p[i].y));//求最小距离最大if(tmp>ans) {ans=tmp;ansx=x,ansy=y;}return tmp;
}void climbhill() {double now_x=ansx,now_y=ansy;for(double T=1e7;T>=1e-7;T*=0.998) {double nxt_x=now_x+len()*T;double nxt_y=now_y+len()*T;if(nxt_x<0||nxt_x>lenx||nxt_y<0||nxt_y>leny)continue;if(calc(now_x,now_y) 模拟退火代码如下：
#include
#include
#include
#include
using namespace std;#define sqr(x) ((x)*(x))const double T_0=1e-7,del_T=0.998;int lenx,leny,n;
double ansx,ansy,ans;int read() {int x=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';return x*f;
}struct point {double x,y;
}p[1001];double len() {double x=rand()%200000-100000;return x/100000;
}double dis(double x1,double y1,double x2,double y2) {return sqrt(sqr(x1-x2)+sqr(y1-y2));
}double calc(double x,double y) {double tmp=1e18;for(int i=1;i<=n;i++)tmp=min(tmp,dis(x,y,p[i].x,p[i].y));if(tmp>ans) {ans=tmp;ansx=x;ansy=y;}return tmp;
}void Anneal() {double T=1e7,now_x=ansx,now_y=ansy;while(T>=T_0) {double nxt_x=now_x+len()*T;double nxt_y=now_y+len()*T;if(nxt_x<0||nxt_x>lenx||nxt_y<0||nxt_y>leny) {T*=del_T;continue;//不这么写直接卡死循环了……}double tmp1=calc(now_x,now_y);double tmp2=calc(nxt_x,nxt_y);if(tmp2>tmp1||exp((tmp2-tmp1)/T)*RAND_MAX>rand())now_x=nxt_x,now_y=nxt_y;T*=0.998;}
}int main() {srand(time(0));int T=read();while(T--) {lenx=read(),leny=read(),n=read();ans=-1e18;ansx=lenx/2;ansy=leny/2;for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);Anneal();printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy);}return 0;
} 程序仅供参考
转载于:https://www.cnblogs.com/AKMer/p/9599381.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！