题解：P12617 [RMI 2023] Circles

· · 题解

为什么需要李超树？送一个 O(nm) 的做法。

题意

求出格点最大内接圆。要求在圆心也在格点上。n, m \le 3000

另外别管那个“半径为正整数”，是错误翻译，我找了罗马尼亚语题面，只说了正坐标。

题解

把不可挖格子的四个角以及平面边界上的整数点都作为源点，令源点距离为 0，其余为 +\infty。 对每个整数格点 (x,y)，答案半径平方就是它到最近源点的平方欧氏距离：

D(x, y) = \min_{(p, q)\in S} \left \{ (x - p)^2 + (y - q)^2 \right \}.

直接做是 O(n^2 m^2)，考虑优化。具体的，因为两维关系不大，考虑分离两维：

D(x, y) =\min_{q} \left \{ (y - q)^2 + \underbrace{\min_{p} \left \{ (x - p)^2 + \delta(p, q) \right \} }_{g(x, q)} \right \}

其中 \delta(p, q) 若 (p, q) \in S 则为 0，否则为 + \infty。

于是整个计算可以分成两个一维变换（按 D 指导的话来说，是 EDT（Euclidean Distance Transform））。

EDT

对于这样一个式子：

b_j=\min_{i} \left \{ a_i + (i - j)^2 \right \}

我们是可以用斜率优化解决的。具体的，我们把它拆开来：

a_i + (i - j)^2 = j^2 + \underbrace{(a_i + i^2) - 2 i \cdot j}_{L_i(j)}.

其中 L_i(x) 为一次函数。其斜率 -2 i 随着 i 增大单调递减，所以可以提前处理出凸包。

而我们查询的 j 单调递增，可以用决策点单调性做到线性。

所以从 \delta(p, q) 开始，两维各做一次 EDT 就行了。答案取最大半径。

Code

#include <bits/stdc++.h>
#include <cassert>
using ll = long long;

const int N = 3005;
int n, m, qu[N];
ll f[N][N], lk[N], lb[N];
char s[N][N];

void edt0(ll *g) {
    int r = 0;
#define ed qu[r]
#define ex qu[r - 1]
    for (int i = 0; i <= m; ++i) {
        lk[i] = -2 * i; lb[i] = g[i] + i * i;
        while (1 < r && (lb[i] - lb[ex]) * (lk[ed] - lk[i]) >= (lb[ed] - lb[i]) * (lk[i] - lk[ex])) --r;
        qu[++r] = i;
    }

    int l = 1;
#define be qu[l]
#define bx qu[l + 1]
    for (int i = 0; i <= m; ++i) {
        while (l < r && lb[be] + lk[be] * i >= lb[bx] + lk[bx] * i) {
            ++l;
        }
        g[i] = lb[be] + lk[be] * i + i * i;
    }
}

void edt1(int p) {
    int r = 0;
    for (int i = 0; i <= n; ++i) {
        lk[i] = -2 * i; lb[i] = f[i][p] + i * i;
        while (1 < r && (lb[i] - lb[ex]) * (lk[ed] - lk[i]) >= (lb[ed] - lb[i]) * (lk[i] - lk[ex])) --r;
        qu[++r] = i;
    }

    int l = 1;
    for (int i = 0; i <= n; ++i) {
        while (l < r && lb[be] + lk[be] * i >= lb[bx] + lk[bx] * i) ++l;
        f[i][p] = lb[be] + lk[be] * i + i * i;
    }
}

int main() {
#ifdef PANGUN
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    scanf("%d%d", &n, &m); assert(0 <= n && n < N);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    for (int i = 1; i < n; ++i)
        for (int j = 1; j < m; ++j) f[i][j] = 1e12;
    for (int i = 0; i <= n; ++i) f[i][0] = 0;
    for (int i = 0; i <= n; ++i) f[i][m] = 0;
    for (int i = 0; i <= m; ++i) f[0][i] = 0;
    for (int i = 0; i <= m; ++i) f[n][i] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (s[i][j] == '0')
                f[i][j] = f[i - 1][j] = f[i][j - 1] = f[i - 1][j - 1] = 0;

    for (int i = 0; i <= n; ++i) edt0(f[i]);
    for (int i = 0; i <= m; ++i) edt1(i);
    int x = 0, y = 0; ll ans = 0;
    for (int i = n; i >= 0; --i)
        for (int j = m; j >= 0; --j)
            if (f[i][j] >= ans) {
                ans = f[i][j];
                x = j; y = i;
            }
    printf("%d %d %lld\n", x, y, ans);
    return 0;
}

另外模拟赛出了这题，题意不清，我按照原题的理解写了，结果被诈骗，或成最大冤种。