首页 > 其他分享 >模拟退火

模拟退火

时间:2023-02-17 16:25:40浏览次数:41  
标签:int double long re 模拟退火 y1 define

有时间再修

OI_wiki

学习blog

P1337 [JSOI2004] 平衡点 / 吊打XXX

点击查看代码
#include<bits/stdc++.h>
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
#define Rd (T*(rand()*2-RAND_MAX))
using namespace std;
cs int N=1009;
cs long double D=0.92,eps=1e-14;
int n;
long double x[N],y[N],w[N],bx,by;
il long double calc(long double _x0,long double _y0)
{
	long double re=0;
	for(ri int i=1;i<=n;++i)
		re+=sqrt((x[i]-_x0)*(x[i]-_x0)+(y[i]-_y0)*(y[i]-_y0))*w[i];
	return re;
}
il void sa()
{
	long double T,_x0,_y0,_x1,_y1,re,ans,bst; int times=1;
	bst=ans=calc(bx/=n,by/=n); srand(time(0));
	while(times--)
	{
		ans=bst,_x0=bx,_y0=by;
		for(T=1e5;T>eps;T*=D)
		{
			_x1=_x0+Rd,_y1=_y0+Rd,re=calc(_x1,_y1);
			if(bst>re) bst=re,bx=_x1,by=_y1;
			if(ans>re||exp((ans-re)/T)>(long double)rand()/RAND_MAX)
				ans=re,_x0=_x1,_y0=_y1;
		}
	}
	printf("%.3Lf %.3Lf\n",bx,by);
}
signed main()
{
	scanf("%d",&n);
	for(ri int i=1;i<=n;++i)
		scanf("%Lf%Lf%Lf",&x[i],&y[i],&w[i]),bx+=x[i],by+=y[i];
	sa();
	return 0;
}

标签:int,double,long,re,模拟退火,y1,define
From: https://www.cnblogs.com/Bertidurlah/p/17130539.html

相关文章