模拟退火学习笔记 & luogu P1337 [JSOI2004]平衡点 / 吊打XXX
背景:
先放一放动态点分治。
开启模拟退火。
题目传送门:
https://www.luogu.org/problemnew/show/P1337
题意:
有个物体质量为用根绳子通过个洞系在一个结上,求这个结在平面中的位置。
长这样:
思路:
前置物理知识:对于一个系统(物体)来说,如果其能量越小,则越稳定。原谅我无知,不会表达。
那就好办了,我们可以认为这些重物只受重力。
那么假设结的位置为,则
为了使系统越稳定,就要使尽可能小。那么找到这个的最小值即可。
借助非正解模拟退火或模拟退火即可。
代码:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define eps 1e-16
using namespace std;
int n;
double ansx,ansy;
struct node{int x,y,z;} a[1010];
double calc(double x,double y)
{
double sum=0;
for(int i=1;i<=n;i++)
sum+=sqrt((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y))*a[i].z;
return sum;
}
void fire()
{
double t=200;
while(t>eps)
{
double nowx=ansx+(rand()*2-RAND_MAX)*t,nowy=ansy+(rand()*2-RAND_MAX)*t;
double delta=calc(nowx,nowy)-calc(ansx,ansy);
if(delta<0||exp(-delta/t)*RAND_MAX>rand()) ansx=nowx,ansy=nowy;
t*=0.898;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);
random_shuffle(a+1,a+n+1);
for(int i=1;i<=20;i++)
fire();
printf("%.3lf %.3lf",ansx,ansy);
}