Luogu P1337 [JSOI2004]平衡点 / 吊打XXX

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
inline double calc(double x, double y) {/* ... */}
double ansval = INF, ansx, ansy;
void SA() {
    double tem = MAXx;
    double nowx = rdom(-MAXx, MAXx), nowy = rdom(-MAXx, MAXx);
    double nowval = calc(nowx, nowy);
    double nexval, nexx, nexy;
    while (tem > 1e-10) {
        nexx = nowx + rdom(-tem, tem); nexy = nowy + rdom(-tem, tem);
        nexval = calc(nexx, nexy);
        if (nowval > nexval || exp((nowval - nexval) / tem) > rdom()) {
            nowval = nexval;
            nowx = nexx; nowy = nexy;
            if (ansval > nowval) {
                ansval = nowval;
                ansx = nowx; ansy = nowy;
            }
        }
        tem *= 0.999;
    }
}

signed main() {
    int bg1 = clock();
    srand(time(0));
    // ...
    int bg2 = clock();
    SA();
    int times = clock() - bg2;
    while (CLOCKS_PER_SEC - clock() + bg1 > times + 20000) {
        SA();
    }
}