模拟退火

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int ans = 0;
i64 x[11], y[11], r[11], p[1005], q[1005];
int main() {
    srand(time(0));
    int n, m, R;
    cin >> n >> m >> R;
    for (int i = 1 ; i <= n ; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }
    for (int i = 1 ; i <= m ; i++) {
        cin >> p[i] >> q[i];
    }
    auto dist = [&](double x1, double y1, double x2, double y2) {
        return (double) sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    };
    auto get = [&](double sx, double sy) {
        double miR = R;
        for (int i = 1 ; i <= n ; i++) {
            miR = min(miR, dist(sx, sy, x[i], y[i]) - r[i]);
        }
        int cnt = 0;
        for (int i = 1 ; i <= m ; i++) {
            if (dist(sx, sy, p[i], q[i]) <= miR) {
                cnt++;
            }
        }
        ans = max(ans, cnt);
        return cnt;
    };
    auto rnd = [&](int L, int R) {
        return rand() % (R - L + 1) + L;
    };
    auto sa = [&]() {
        int pos = rnd(1, m);
        double nx = p[pos], ny = q[pos];
        int now = get(nx, ny);
        for (double t = 3000 ; t >= 1e-8 ; t *= 0.99) {
            double mx = nx + t * rnd(-1000, 1000), my = ny + t * rnd(-1000, 1000);
            int tnow = get(mx, my);
            if (tnow > now || exp(10000 * (tnow - now) / t) > 1.0 * rand() / RAND_MAX) {
                nx = mx;
                ny = my;
                now = tnow;
            }
        }
    };
    while(1.0 * clock() / CLOCKS_PER_SEC < 0.9) {
        sa();
    }
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int n, m;
int a[25], sum[25];
double dp[25][8], avg;
double ans = 1e9;
double get() {
    for (int i = 1 ; i <= n ; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 0 ; i <= n ; i++ ){
        for (int j = 0 ; j <= m ; j++) {
            dp[i][j] = 1000000;
        }
    }
    dp[0][0] = 0;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= min(i, m) ; j++) {
            for (int k = 1 ; k <= i ; k++) {
                double res = sum[i] - sum[k - 1] - avg;
                res *= res;
                dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + res);
            }
        }
    }
    ans = min(ans, dp[n][m]);
    return dp[n][m];
}
int main() {
    srand(time(0));
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        avg += a[i];
    }
    avg /= m;
    auto rnd = [&](int L, int R) {
        return rand() % (R - L + 1) + L;
    };
    auto sa = [&]() {
        double now = ans;
        for (double t = 5000 ; t >= 1e-8 ; t *= 0.99) {
            int x, y;
            do {
                x = rnd(1, n);
                y = rnd(1, n);
            } while (x == y);
            swap(a[x], a[y]);
            double tnow = get();
            if (tnow < now || exp((now - tnow) / t) > 1.0 * rand() / RAND_MAX) {
                now = tnow;
            } else {
                swap(a[x], a[y]);
            }
        }
    };
    while(1.0 * clock() / CLOCKS_PER_SEC < 0.9) {
        sa();
    }
    cout << fixed << setprecision(2) << sqrt(ans / m) << "\n";
    return 0;
}