吊打XXX

wjh15101051's space

卧薪尝胆，厚积薄发。

吊打XXX

Date: Fri Aug 10 22:28:36 CST 2018

In Category: NoCategory

Description：

有 $n$ 个重物，每个重物系在一条绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。问绳结最终平衡于何处。

$1\le n \le 1000$

Solution：

模拟退火，每次随即一个移动方向，判断是否更优，不优则以一定概率接受新答案。答案用势能算

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

struct point

{

	double x,y,w;

}p[MAXN];

double ans = 1e18;

double energy(double x,double y)

{

	double res = 0.0;

	for(int i = 1;i <= n;++i)

	{

		double dx = x - p[i].x,dy = y - p[i].y;

		res += sqrt(dx * dx + dy * dy) * p[i].w;

	}

	return res;

}

int main()

{

	srand(time(NULL));

	scanf("%d",&n);

	double x,y;

	for(int i = 1;i <= n;++i)

	{

		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w);

		x += p[i].x;y += p[i].y;

	}

	x /= n;y /= n;

	double t = 1000000,delta = 0.998;

	ans = energy(x,y);

	while(t > 1e-14)

	{

		double newx = x + (double)(rand() * 2 - RAND_MAX) * t;

		double newy = y + (double)(rand() * 2 - RAND_MAX) * t;

		double newans = energy(newx,newy);

		if(newans < ans)

		{

			ans = newans;

			x = newx;y = newy;

		}

		else

		{

			if(exp((ans - newans) / t) * RAND_MAX > rand())

			{

				x = newx;y = newy;

			}

		}

		t = t * delta;

	}

	t = 1000000,delta = 0.998;

	while(t > 1e-14)

	{

		double newx = x + (double)(rand() * 2 - RAND_MAX) * t;

		double newy = y + (double)(rand() * 2 - RAND_MAX) * t;

		double newans = energy(newx,newy);

		if(newans < ans)

		{

			ans = newans;

			x = newx;y = newy;

		}

		else

		{

			if(exp((ans - newans) / t) * RAND_MAX > rand())

			{

				x = newx;y = newy;

			}

		}

		t = t * delta;

	}

	printf("%.3lf %.3lf\n",x,y);

	return 0;

}

In tag: 算法-模拟退火

wjh15101051