简单模拟退火求调
查看原帖
简单模拟退火求调
378467
Windy_YY楼主2024/11/29 15:44

rt,wa on 4,但是和答案差别不到 10610^{-6}

int x[N], y[N];
// dist^2
int dist(int x, int y, int xx, int yy) {
    return (x - xx) * (x - xx) + (y - yy) * (y - yy);
}
int w, h, n;
int chk(int xx, int yy) {
    int m1 = 4e18, m2 = 4e18;
    for (int i = 1; i <= n; ++i) {
        int fin = dist(xx, yy, x[i], y[i]);
        if (fin < m1) m2 = m1, m1 = fin;
        else if (fin < m2) m2 = fin;
    }
    return m2;
}
void run() {
    srand(time(0));
    w = read(), h = read(), n = read();
    for (int i = 1; i <= n; ++i) x[i] = read(), y[i] = read();
    long double x = Rand(0, w), y = Rand(0, h);
    int last = chk(x, y), mx = last;
    while (1. * clock() / CLOCKS_PER_SEC <= 1.75) {
        for (long double tem = 1e6; tem >= 1e-12; tem *= 0.999) {
            long double xx = Rand(max(0.0L, x - tem), min((long double)w, x + tem)), yy = Rand(max(0.0L, y - tem), min((long double)h, y + tem));
            int now = chk(xx, yy), delta = last - now;
            mx = max({mx, now, last});
            if (delta < 0 || Rand(0, 1) < exp(-delta / tem)) x = xx, y = yy, last = now;
            // cout << "qwq " << Rand(0, 1) << ' ' << expl(-delta / tem) << ' ' << delta << ' ' << tem << '\n'; _sleep(250);
        }
    }
    printf("%.25Lf\n", sqrtl(mx));
}
2024/11/29 15:44
加载中...