题目大意

CCPC 2023 Guangdong Provincial M - Computational Geometry（CF Gym 104369 镜像）。

给定逆时针顺序凸 $N$ 边形顶点 $A_0, A_1, \ldots, A_{N-1}$ ，选两个不相邻的顶点 $A_{i_1}, A_{j_1}$ 把多边形切成两段 sub-polygon $Q$ 和 $R$ ，最小化

\mathrm{diam}(Q)^2 + \mathrm{diam}(R)^2

数据范围 $N \le 5000$ ，多组数据。

样例

$N = 4$ ， $\{(1,0), (2,0), (1,1), (0,0)\}$ ，期望 $\mathbf{4}$ ：切 $(0, 2)$ 把菱形切成两个三角形，每半 $d^2 = 2$ 。
$N = 6$ ，spike-3 hull，期望 $\mathbf{44}$ ：切 $(2, 4)$ ， $Q$ 直径 $^2 = 10$ 、 $R$ 直径 $^2 = 34$ 。

思路讲解

普通 RC 求凸多边形直径为什么对

直观理解：拿一把卡尺（两条平行 supporting line）夹住凸多边形旋转一圈，最大间距就是直径。算法上对应「外循环 r 跑遍每条边、内层 l 跟随推进」——每条边都被卡过一遍，所以直径必出现在某次「边-反极顶点」的 candidate 里，必被 collect。

本题改造为什么有问题——边覆盖不全

子弧 + 闭合 chord 是一个闭子多边形 $R'$ ，对它跑经典 RC 是对的——但前提是把 $R'$ 的所有边都卡过。

我的改造里 edge 从 $i$ 起步靠 need_edge_move 单调向前推进，永远停留在原多边形的相邻顶点对 $(A_e, A_{e+1})$ 上。但 $R'$ 的边集 = 子弧上的原边 + 一条非相邻的 chord $(A_j, A_i)$ ——chord 是非相邻顶点对，edge 数值永远不会取到它。

卡尺没把 $R'$ 的所有边卡过一遍，自然漏直径。

区间 DP 正解

状态

$\mathrm{dp}[i][j]$ = 以子弧 $A_i \to A_{i+1} \to \cdots \to A_j$ （CCW 沿原多边形顺序，含两端）为顶点集的闭子多边形的直径² ——即该顶点集上所有点对的 $\|A_p - A_q\|^2$ 最大值。

递推

\mathrm{dp}[i][j] = \max\big(\,\mathrm{dp}[i{+}1][j],\ \mathrm{dp}[i][j{-}1],\ \|A_i - A_j\|^2\,\big)

正确性：把顶点集 $\{i, i{+}1, \ldots, j\}$ 上所有无序点对 $(p, q)$ 按是否含两端点 $i, j$ 分三类：

不含 $i$ ：点对 $\subseteq \{i{+}1, \ldots, j\}$ ，覆盖在 $\mathrm{dp}[i{+}1][j]$
不含 $j$ ：点对 $\subseteq \{i, \ldots, j{-}1\}$ ，覆盖在 $\mathrm{dp}[i][j{-}1]$
两端都含：唯一点对 $(i, j)$ ，单独的 $\|A_i - A_j\|^2$ 项

三类不重不漏、取 max 即全集直径²。

为什么 DP 走得通、RC 走不通

关键对比：这个递推式完全不依赖凸性——它就是个「枚举所有点对取 max」的 $O(N^2)$ 朴素 DP。「凸」在 RC 路线里是刚需（卡尺单峰让对蹵点单调推进 → $O(N)$ ）；DP 路线不贪「凸」这点便宜、只用上「顶点集是连续子弧」这个事实。一句话：RC 吃结构红利换 $O(N)$ ，DP 不吃红利 $O(N^2)$ 但保命。

循环顺序是硬约束

跟一般区间 DP 一样：len 在外、 $i$ 在内。奇心把 $i$ 写在外会踩心路历程 7 那个坑（ $2N$ pass 兜底也救不回）。

切法枚举

枚举不相邻顶点对 $(i_1, j_1)$ 作为 chord：

\mathrm{ans} = \min_{j_1 \ge i_1 + 2,\ j_1 \not\equiv i_1 \pm 1 \pmod N} \big(\,\mathrm{dp}[i_1][j_1] + \mathrm{dp}[j_1][i_1]\,\big)

两项分别是切后两段子弧的直径²——dp 表索引是循环的， $\mathrm{dp}[j_1][i_1]$ 自动覆盖另一段。cross 检查 $\ne 0$ 顺手筛掉两类退化： wrap-adjacent切（如 $(0, N-1)$ 在循环视角下其实是相邻点），与共线退化切（chord 踩在原多边形某条边上）。

复杂度

填 dp 表 $O(N^2)$ 个状态 × $O(1)$ 转移、枚举切法 $O(N^2)$ 、总 $O(N^2)$ 。 $N \le 5000$ 下填表 $2.5 \times 10^7$ 次贴近 TL，多组数据下实测 3312 ms / 6s 限制。

AC 代码

AC 提交：codeforces.com/gym/104369/submission/373844988

切到 $O(N^2)$ 区间 DP 后 AC（3312 ms / 192600 KB， $N \le 5000$ 多组数据贴近 TL）。

展开 Solve() 与 distancePPNorm 的核心实现

// dp[i][j] = 子弧 A_i → A_j（CCW，含两端）的凸子多边形直径²
// 递推：dp[i][j] = max(dp[i+1][j], dp[i][j-1], ‖A_i - A_j‖²)
// 关键：len 外、i 内 —— len 大的依赖 len 小的，i 在外的话同 len 不同起点的
//       dp[i+1][·] 还没填过，单遍跑不出来；2N pass 兜底也是错觉

auto distancePPNorm(const Point &a, const Point &b) {
    return (a - b).norm();  // 返回平方距离，不开根
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<vector<ull>> dp(N, vector<ull>(N));
    for (int len = 1; len < N; ++len) {
        for (int i = 0; i < N; ++i) {
            int ip1 = (i + 1) % N;
            int j = (i + len) % N;
            int j_1 = (i + len - 1) % N;
            if (len == 1) { dp[i][j] = distancePPNorm(A[i], A[j]); continue; }
            dp[i][j] = max({dp[ip1][j], dp[i][j_1], (ull) distancePPNorm(A[i], A[j])});
        }
    }
    // 枚举切法 (i1, j1)，分多边形为子弧 [i1..j1] 与 [j1..i1+N]
    ull ans = ~0ULL;  // ⚠️ 不能用 INF=(1ll<<61)-1，被 1.6e19 候选反超 → WA on test 7
    for (int i1 = 0; i1 < N; ++i1) {
        int j2 = i1;
        for (int j1 = i1 + 2; j1 < N; ++j1) {
            int i2 = j1;
            // cross != 0 顺手筛掉 wrap-adjacent (0, N-1) 与共线退化切
            if (cross(A[i1], A[(i1+1)%N], A[j1]) != 0
             && cross(A[i2], A[(i2+1)%N], A[j2]) != 0) {
                ans = min(ans, dp[i1][j1] + dp[i2][j2]);
            }
        }
    }
    cout << ans << "\n";
}

心路历程

直觉把「凸多边形直径 → 旋转卡壳」和「切法枚举」硬嫁接，写出 vanilla RC + 子弧增长版
sample 1 ( $n=4$ ) 期望 $4$ 实测 $3$ ，开始 debug
第一发现： $\mathrm{dp}[2][0] = 1$ 漏了 $(A_2, A_3)$ 这对距离——up 起步 $i+2$ ，arc 起点附近的 pair 永远不进 candidate
第二发现：dp[edge][up] = ans 索引用动态 edge 而非外层切起点 $i_\mathrm{outer}$ ，dp 矩阵大量被错位写入（附带 bug）
spike-3 对拍反例（差 $7.45\%$ ）让「算法是结构性错的、不是 off-by-one」心服口服
抓到根因：RC 之所以对，因为它每条边都卡过 + 每个顶点都反极过；改造版两条都破了
DP 重写又踩循环顺序坑——RC 死了之后转 $O(N^2)$ 区间 DP（ $\mathrm{dp}[i][j]$ = 子弧 $A_i \to A_j$ 凸子多边形直径² ），递推 $\mathrm{dp}[i][j] = \max(\mathrm{dp}[i+1][j],\ \mathrm{dp}[i][j-1],\ \|A_i - A_j\|^2)$ 。第一发先把 $i$ 写在外、 $\mathrm{len}$ 写在内，再跑 $2N$ 遍当兜底——错：

当前算 $\mathrm{dp}[i][j]$ 需要 $\mathrm{dp}[i+1][j]$ （len $-1$ 但起点变了）。 $i$ 外 len 内的顺序下，处理 $i=0$ 时 $\mathrm{dp}[1][\cdot]$ 整行都还是 $0$ ，根本没轮到 $i=1$ 那层
$2N$ pass 兜底也救不回来：pass 1 全程用 $0$ 推导出脏值；pass 2 处理 $i=0,\ \mathrm{len}=3$ 时要 $\mathrm{dp}[1][3]$ ，可这个值是 pass 1 用 $\mathrm{dp}[2][3]=0$ 算出来的脏值——pass 2 来不及修
正确写法：len 外、 $i$ 内，一遍即可

心法：「len 小的之前都被计算了」这个直觉成立的前提是 len 在外。 $i$ 在外的话，给定 $i$ 你确实按 len 升序填了 $\mathrm{dp}[i][\cdot]$ ，但同 len 不同起点的 $\mathrm{dp}[i+1][\cdot]$ 还压根没碰过——「 $2N$ pass 兜底」是错觉：每跑一遍正确性最多渗透一层 len，最坏要 $N$ 遍且仍受脏值污染。

附件

详细 debug 记录与图示见下方嵌入 PDF —— rc_breakdown.pdf ，5 页，含凸多边形 + 反极顶点单峰示意 / 闭子多边形 $R'$ / forbidden up + chord $\times$ 标记 / $\mathrm{dp}[3][1]$ trace 表。

rc_breakdown.pdf — 5 页 debug 记录：经典 RC 为什么对（凸多边形 + 反极顶点 + 距离单峰）/ 闭子多边形 R’ / forbidden up + chord ✗ 标记 / dp[3][1] trace 表

Znzryb's Blog

CCPC 2023 Guangdong M - Computational Geometry（不是旋转卡壳）