题目链接：传送门

Description

如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。 问绳结X最终平衡于何处。 注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

Input

文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0 < w≤1000 )

Output

你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。

Sample Input

3 0 0 1 0 2 1 1 1 1

Sample Output

0.577 1.000

Solution

人生第一道计算几何/模拟退火题 ~~ ~~虽然好像有点水。。。 ~~ ~~我们首先确定一个原点，然后在这个原点上进行正交分解， 最终我们可以得到一个合力，而真正的平衡点一定在合力所指的方向 接着把平衡点向合力方向调整一个尺度k，k是自定的一个常数，且随着调整次数的增多而不断减小 ~~ ~~于是这样就可以求得近似解

19.2.28 UPD

假的假的，什么鬼模拟退火，就是个爬山。。。

找时间写一篇真的模拟退火。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Maxn = 1000 + 100;
const double eps = 1e-5;
int N;
struct node
{
    double x, y, f;
}Object[Maxn];
double Move = 5000;
double x, y;
inline double sqr(double x)
{
    return x * x;
}
int Dx = 1, Dy = 1;
inline void Work()
{
    double Fx = 0, Fy = 0, Dis = 0;
    for (int i = 1; i <= N; ++i)
    {
        Dis = sqrt(sqr(x - Object[i].x) + sqr(y - Object[i].y));
        if (Dis == 0.0)
            continue;
        Fx += Object[i].f * (Object[i].x - x) / Dis;
        Fy += Object[i].f * (Object[i].y - y) / Dis;
    }
    double F = sqrt(sqr(Fx) + sqr(Fy));
    x += Move * Fx / F;
    y += Move * Fy / F;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) scanf("%lf%lf%lf", &Object[i].x, &Object[i].y, &Object[i].f);
    while (1)
    {
        double sx = x;
        double sy = y;
        Work();
        if (abs(sx - x) <= eps && abs(sy - y) <= eps) break;
        if (Dx != (x > sx) || Dy != (y > sy))
        {
            Dx = !(x > sx);
            Dy = !(y > sy);
            Move *= 0.9;
        }
    }
    printf("%.3lf %.3lf\n", x, y);
    return 0;
}