P1337 [JSOI2004]平衡点 / 吊打XXX 模拟退火

模拟退火模板题,不会可以看这里

一个位置到所有点的dis*weight的和越小越好

include

include

include

include

include

define DB long double

define YY T(2rand()-RAND_MAX)

using namespace std;
int n,Time=1;
DB sx,sy,ans,Ans,X0,Y0,X1,Y1,tmp;
const int N=1010;
const DB D=0.97,eps=1e-14;
DB x[N],y[N],w[N];
DB p2(DB x){return xx;}
DB suan(DB X,DB Y)
{
DB res=0;
for(int i=1;i<=n;++i)
res+=sqrt(p2(X-x[i])+p2(Y-y[i]))
w[i];
return res;
}
int main()
{
srand(20030701);cin>>n;
for(int i=1;i<=n;++i)
{
scanf("%Lf%Lf%Lf",&x[i],&y[i],&w[i]);
sx+=x[i];sy+=y[i];
}
sx/=n;sy/=n;Ans=ans=suan(sx,sy);
while(Time--)
{
ans=Ans;X0=sx;Y0=sy;
for(DB T=100000;T>eps;T*=D)
{
X1=X0+YY;Y1=Y0+YY;tmp=suan(X1,Y1);
if(tmp<Ans)Ans=tmp,sx=X1,sy=Y1;
if(tmp<ans||exp((ans-tmp)/T)>(DB)rand()/RAND_MAX)ans=tmp,X0=X1,Y0=Y1;
}
}
printf("%.3Lf %.3Lf",sx,sy);
return 0;
}

原文地址:https://www.cnblogs.com/wljss/p/14966943.html