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 <cmath>

#include <ctime>

#include <cstdio>

#include <algorithm>

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)<calc(nxt_x,nxt_y))

			now_x=nxt_x,now_y=nxt_y;

	}

}

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);

		climbhill();

		printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy);

	}

	return 0;

}

模拟退火代码如下：

#include <cmath>

#include <ctime>

#include <cstdio>

#include <algorithm>

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;

}

程序仅供参考

巴特西

POJ1379：Run Away

最新文章

热门文章