题解 P5544

PragmaGCC · 2021-07-23 22:24:12 · 题解

首先，对于一个点，它的半径肯定要取到能到达的最远距离。所以我们可以对于一个点直接计算答案。

然后就可以跑模拟退火了。每次在原答案的基础上随机一个点，随机一个概率来判断是否要保留新答案。随着温度 T 的减小逐渐趋近到峰值。

具体来说，我们每次随机一个变化量，将原位置 (x,y) 位移至 (x',y')。计算这个新位置的答案。如果比原答案优就更新答案。否则，概率地保留原答案或更新。

注意题目要求的是最大值，应写成 (delta > 0) || (exp(-delta / T) * RAND_MAX < rand())。

tip:为提高答案准确率，最初的点可选为所有点的平均值，以减少尝试次数。

感谢 @空与灵之白 题解中的参数。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
const int N = 1005;
int n, m, R;
typedef long double ld;
struct point { // 圆，点可视为 r=0
    ld x, y, r;
} a[N], b[N];
ld ansx, ansy, ans; // 答案坐标和值
ld getdis(ld fx, ld fy, ld gx, ld gy) { // 计算两点距离
    return sqrt((fx - gx) * (fx - gx) + (fy - gy) * (fy - gy));
}
ld calc(ld fx, ld fy) { // 计算答案
    ld d = R, ret = 0;
    for (int i = 1; i <= n; i++) {
        d = min(d, getdis(fx, fy, a[i].x, a[i].y) - a[i].r);
    }
    for (int i = 1; i <= m; i++) {
        if (getdis(b[i].x, b[i].y, fx, fy) <= d) ret++;
    }
    return ret;
}
void SA() {
    for (ld T = 20060, nx, ny; T > 1e-18; T *= 0.9976) {
        nx = ansx + (rand() * 2 - RAND_MAX) * T,
        ny = ansy + (rand() * 2 - RAND_MAX) * T;
        // 随机数为正整数，这里这样操作保证变化量可以为负数。
        ld delta = calc(nx, ny) - ans;
        if ((delta > 0) || (exp(-delta / T) * RAND_MAX < rand()))
            ansx = nx, ansy = ny, ans = ans + delta;
    }
}
int main(void) {
    srand(114514);
    scanf("%d%d%d", &n, &m, &R);
    for (int i = 1, x, y, w; i <= n; i++) {
        scanf("%d%d%d", &x, &y, &w);
        a[i] = (point){x, y, w};
    }
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        b[i] = (point){x, y, 0};
        ansx += x, ansy += y;
    }
    ansx = ansx / m, ansy = ansy / m; // 初始坐标
    ans = calc(ansx, ansy);
    SA(), SA(), SA(), SA();
    printf("%d\n", (int)ans);
    return 0;
}