题目要求
最小(dis表示绳结到点i的距离),就是个广义费马点的题,模拟退火裸题QAQ
模拟退火就是优化后的爬山算法,一开始先随机一个平均点,接下来如果随机到的点比当前点劣,温度比较高的话也有几率跳过去,这样就能跳出一个局部最优解,随着温度降低,跳到劣点的概率越来越小
好喵喵的算法!
(这题好像黄学长直接爬山算法也过了,模拟退火贼慢T^T
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=,inf=1e9;
int n;
double ans,ansx,ansy;
double x[maxn],y[maxn],g[maxn];
double dis(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
double cal(double xx,double yy)
{
double sum=;
for(int i=;i<=n;i++)sum+=g[i]*dis(xx,yy,x[i],y[i]);
if(sum<ans)ans=sum,ansx=xx,ansy=yy;
return sum;
}
double Rand(){return rand()%/1000.0;}
void sa(double T)
{
double nowx=ansx,nowy=ansy;
while(T>1e-)
{
double nextx=nowx+T*(Rand()*-);
double nexty=nowy+T*(Rand()*-);
double dE=cal(nowx,nowy)-cal(nextx,nexty);
if(dE>||exp(dE/T)>Rand())nowx=nextx,nowy=nexty;
T*=0.991;
}
for (int i=;i<=;i++)
{
double nextx=ansx+T*(Rand()*-);
double nexty=ansy+T*(Rand()*-);
cal(nextx,nexty);
}
}
int main()
{
srand();
scanf("%d",&n);ans=2333333333333333333ll;
for(int i=;i<=n;i++)
{
scanf("%lf%lf%lf",&x[i],&y[i],&g[i]);
ansx+=x[i];ansy+=y[i];
}
ansx/=n;ansy/=n;sa();
printf("%.3lf %.3lf",ansx,ansy);
return ;
}