题解 洛谷P1337 [JSOI2004]平衡点 / 吊打XXX

发表于 | 分类于 | 阅读次数：

题面
题意:在桌子上有$n$个洞,每个洞挂着重量不等的重物,求这些重物用绳子连接起来后绳结会平衡在那个点上

SA模板题
每次从当前解产生一个新的解
如果更优显然直接接受
否则以$e^{-\frac{\Delta}{T}}$的概率接受($T$为当前温度,$\Delta$为解的差)

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
#include <bits/stdc++.h>
using namespace std;
int x[1010], y[1010], w[1010];
int n;
inline double sqr(double x) {return x * x;}
inline double check(double X, double Y) {
    double ans = 0;
    for(int i = 1; i <= n; i++) ans += w[i] * sqrt(sqr(X - x[i]) + sqr(Y - y[i]));
    return ans;
}
double ans, ansx, ansy;
inline void SA() {
    double T = 200, eps = 1e-15, t = 0.998;
    while(T > eps) {
        double newx = ansx + (2 * rand() - RAND_MAX) * T, newy = ansy + (2 * rand() - RAND_MAX) * T;
        double newans = check(newx, newy);
        // cerr << newans << ' ' << ans << endl;
        if(newans < ans) ans = newans, ansx = newx, ansy = newy;
        else if(exp((ans - newans) / T) * RAND_MAX > rand()) ansx = newx, ansy = newy;
        T *= t;
    }
}
int main() {
    srand(time(0));
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d%d", x + i, y + i, w + i);
    for(int i = 1; i <= n; i++) ansx += x[i], ansy += y[i];
    ansx /= n;
    ansy /= n;
    ans = check(ansx, ansy);
    SA();
    SA();
    SA();
    SA();
    SA();
    return printf("%.3lf %.3lf\n", ansx, ansy), 0;
}