题意简述
有n个重物,每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞,然后系在一起。求绳结X最终平衡于何处。
题解思路
模拟退火
每次随机出一个now,和ans比较,若比ans好,则替换,否则一定概率替换
代码
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
const double eps = 1e-15;
struct Point
{
double x, y;
};
struct Node
{
Point p;
int w;
} a[10010];
int n;
double T = 2000, delta;
Point ans, now;
double sqr(double x)
{
return x * x;
}
double calc(Point pp)
{
double s = 0;
for (register int i = 1; i <= n; ++i)
s += sqrt(sqr(pp.x - a[i].p.x) + sqr(pp.y - a[i].p.y)) * a[i].w;
return s;
}
double sa()
{
while (T > eps)
{
now.x = ans.x + (rand() * 2 - RAND_MAX) * T;
now.y = ans.y + (rand() * 2 - RAND_MAX) * T;
delta = calc(now) - calc(ans);
if (delta < 0) ans = now;
else if (exp(-delta / T) * RAND_MAX > rand()) ans = now;
T *= 0.998;
}
}
int main()
{
srand(29);
scanf("%d", &n);
for (register int i = 1; i <= n; ++i)
{
scanf("%lf%lf%d", &a[i].p.x, &a[i].p.y, &a[i].w);
ans.x += a[i].p.x;
ans.y += a[i].p.y;
}
ans.x /= (double)n;
ans.y /= (double)n;
sa();
printf("%.3lf %.3lf", ans.x, ans.y);
}