求调参
查看原帖
求调参
482610
Mortidesperatslav楼主2024/6/5 19:44
#include <bits/stdc++.h>
using namespace std;
int n, m, R, mdelta, mdt;
struct bul {
    int x, y, r;
} a[20005];
struct enm {
    int x, y;
} b[20005];
double dis(int x, int y, int xx, int yy) {
    return sqrt((x - xx) * 1.0 * (x - xx) + (y - yy) * 1.0 * (y - yy));
}
bool check(int x, int y, int R) {
    for (int i = 1; i <= n; i++)
        if (dis(x, y, a[i].x, a[i].y) < fabs(R * 1.0 + a[i].r))
            return 0;

    return 1;
}
int MR(int x, int y) { //not Miller-Rabin
    int l = 0, r = R, ans = -1;

    while (l <= r) {
        int mid = (l + r) >> 1;

        if (check(x, y, mid))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }

    return ans;
}
int gans(int x, int y, int R) {
    int sum = 0;

    for (int i = 1; i <= m; i++)
        if (dis(x, y, b[i].x, b[i].y) <= R * 1.0)
            sum++;

    return sum;
}
double T0 = 1e12, Tk = 1e-8, d = 0.9996;
int ansx = 0, ansy = 0, ans = 0, lans = 0;
void th() {
    double T = T0;

    while (T > Tk) {
        int nx = ansx + rand() % mdelta * (1 - (rand() % 2) * 2),
            ny = ansy + rand() % mdelta * (1 - (rand() % 2) * 2);

        if (abs(nx) > R + mdt)
            nx = 0;

        if (abs(ny) > R + mdt)
            ny = 0;

        //  cout << nx << " " << ny << "\n";
        int RR = MR(nx, ny), nans = gans(nx, ny, RR);

        if (nans > ans)
            ansx = nx, ansy = ny, ans = nans;
        else {
            double gl = exp(-(nans - ans) / T);

            if ((double)rand() / (double)RAND_MAX < gl)
                ansx = nx, ansy = ny, ans = nans;
        }

        lans = max(lans, ans);
        T *= d;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(20100618);
    int st = clock();
    cin >> n >> m >> R;

    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y >> a[i].r;

    for (int i = 1; i <= m; i++) {
        cin >> b[i].x >> b[i].y;
        mdelta = max(mdelta, max(b[i].x, b[i].y));
    }

    mdt = mdelta;

    if (mdelta > 10)
        mdelta /= 10;

    while (clock() - st < 0.5 * CLOCKS_PER_SEC) {
        th();
        lans = max(ans, lans);
    }

    cout << lans;
}
2024/6/5 19:44
加载中...