思路与算法

二维前缀和记录129×129路口公共场所数量，枚举全部中心，用闭合覆盖方形的裁剪矩形和统计最大值及方案数。

正确性说明

每个合法中心恰被枚举一次。其正方形覆盖边界包含在内，裁剪只去掉城市外无路口部分，前缀容斥准确求覆盖数；更新最大值及相等计数即得到全部最优中心。

复杂度

O(129²+n)时间、O(129²)空间，包含网格清零、建前缀和和全部中心枚举。

易错点

覆盖不是欧氏圆；中心必须在0..128路口范围，四边均为闭区间。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int d, n;
    cin >> d >> n;
    vector<vector<long long>> p(130, vector<long long>(130));
    while (n--) {
        int x, y, k;
        cin >> x >> y >> k;
        p[x + 1][y + 1] = k;
    }
    for (int x = 1; x <= 129; x++)
        for (int y = 1; y <= 129; y++)
            p[x][y] += p[x - 1][y] + p[x][y - 1] - p[x - 1][y - 1];
    long long best = -1;
    int cnt = 0;
    for (int x = 0; x <= 128; x++)
        for (int y = 0; y <= 128; y++) {
            int a = max(0, x - d), b = max(0, y - d), c = min(128, x + d) + 1,
                e = min(128, y + d) + 1;
            long long v = p[c][e] - p[a][e] - p[c][b] + p[a][b];
            if (v > best) {
                best = v;
                cnt = 1;
            } else if (v == best)
                cnt++;
        }
    cout << cnt << ' ' << best << "\n";
}