CCPC 河南 2025 L - Astral Decay

vjudge 链接 · Codeforces Gym 原题 · 2025 CCPC 河南省赛 & 全国邀请赛（郑州，黄河科技学院）

题目大意

二维平面上 n 个互不相同的点（1 ≤ n ≤ 6666，坐标 |x|, |y| ≤ 10⁹）。从这 n 个点中有放回地选 3 个点，标记为 A, B, C，最小化点积：

$$\overrightarrow{AB} \cdot \overrightarrow{AC} = (x_B - x_A)(x_C - x_A) + (y_B - y_A)(y_C - y_A)$$

A, B, C 可以选相同的点，所以答案的下界是 0（取 A = B = C 任意点都给 0）。

输入 / 输出 / 数据范围

• 第 1 行：n（1 ≤ n ≤ 6666）

• 后 n 行：每行 x y（|x|, |y| ≤ 10⁹）

• 输出一行一个整数，最小点积（可能为负，需要 long long / int128）

样例 1

5
0 2
0 -2
3 0
-3 0
0 -1

输出 -8（最优 A = p5 = (0, -1)（hull 内部点）、B = p3 = (3, 0)、C = p4 = (-3, 0)，dot = 3·(-3) + 1·1 = -8）。

思路讲解

一句话

凸包 + 双指针的「投影版」：B、C 都在凸包上（调整法证），固定 A 后让 B 沿 hull CCW 走、C 用双指针单调跟进。整体 O(n·h) ≤ O(n²)。

⚠️ 关键边界（test 44 WA 根因）：A 在凸包顶点上时，B 的起点必须是 A 的 CCW 后继 A_next，不能从 hull[0] 起步——否则方向序断层破坏双指针单调性。光「跳过 B = A」治标不治本。

把"最小点积"翻译成"在某方向上最极端"

固定 A，把点积写成投影形式：

$$\overrightarrow{AB} \cdot \overrightarrow{AC} = |\overrightarrow{AB}| \cdot \mathrm{proj}_{\overrightarrow{AB}}(\overrightarrow{AC})$$

其中 proj 是 AC 在方向 AB 上的有向投影长度（同向为正、反向为负）。要让点积越负越好，就要让 AC 在方向 -AB 上的距离越远越好。

关键不变量：凸集上线性函数的极值在顶点取到。所以最优 C 必然在凸包上；对称地 B 也在凸包上。

但 A 自己不一定在凸包上！ 样例 1 的最优 A = (0, -1) 就在 hull 内部（题目唯一的内部点）。这是「必须枚举所有原始点当 A、不能只在 hull 上枚举 A」的原因——一个非常容易写错的实现细节。

算法三阶段

阶段	干什么	跳过的代价
1. 凸包预处理	对全部 n 个点跑 Andrew O(n log n)	B/C 在全集枚举 → O(n³) TLE
2. 枚举 A	对原始点集（不是 hull）每点当 A	只在 hull 上枚举 A → 漏内部最优 A（样例 1 答案变 -7 而不是 -8）
3. 双指针扫 (B, C)	固定 A 后 B 沿 hull CCW 走、C 单调跟进	二重循环 → O(n·h²) 大数据 TLE

阶段 2 / 3 的「分裂」是核心理解点：枚举的是原始点（n 个），扫的是凸包上的点（h 个），两者不一样。

双指针单调性 = 旋转卡壳的对偶

固定 A，写出内层「对 B 求 C」函数：

$$C^*(B) = \arg\min_{C \in H}\; \overrightarrow{AB} \cdot \overrightarrow{AC} = \arg\min_{C \in H}\; |\overrightarrow{AB}| \cdot \mathrm{proj}_{\overrightarrow{AB}}(\overrightarrow{AC})$$

C*(B) 就是凸包在方向 -AB 上的支撑点。

灵魂对偶：本题就是旋转卡壳的「投影版」——卡壳卡的是「到边的距离」，本题卡的是「沿方向的有向投影」，主结构同构。

结构件	旋转卡壳（求直径）	本题（最小点积）
主循环对象	凸包边 e_i	凸包顶点 B（视作方向 AB）
跟进对象	对踵点 C*（离 e_i 最远）	支撑点 C*（方向 -AB 上最远）
单调性根源	e_i 法方向沿 H 单调旋转	AB 方向随 B 沿 H 单调旋转
判定工具	cross 比 C 到边距离	dot 比 C 沿 AB 投影

A 在凸包上时的边界处理（test 44 WA 根因）

这一节是 ICPC 题解里最容易写错的点，也是题解 PDF 一笔带过那句的真意：

如果 A 在凸包上，枚举 B 时就不要枚举 A 了，从 A 的下一个点开始枚举 B，转回来到 A 的上一个点结束枚举。 —— 命题组 sol.pdf

为什么不能"光跳过 B = A"了事

if (A.id == convex[b].id) continue; 只解决 AB = 0 退化（该轮 dot 全是 0），没解决方向序断层。

真正的死因：双指针单调性要求「随 B 沿 hull 走，方向 AB 必须单调旋转」，这样 C* 才能跟着单向推进。当 A 在 hull 顶点 h_{i_A} 上时，按 hull 原序 [h_0, h_1, ..., h_{h-1}] 遍历 b：

• h_0, h_1, ..., h_{i_A - 1} 这一段在「从 A 看的 CCW 极角序」里属末段

• 真正的 CCW 起点是 h_{i_A + 1}（A 的 next）

代码从 h_0 起扫等于「方向倒着来」，下一步跳到 h_{i_A + 1} 时方向回退 90° 以上，C* 单向 c++ 跟不上 → WA。

实证反例（17 点，本会话抓到）

17
16 100
104 -9
-18 94
-86 45
-87 -47
54 89
-30 -94
-60 -78
52 -90
2 -103
-98 9
-97 -14
96 -36
74 67
-61 83
96 31
65 -72

真最优：A = p11 = (-97, -14)（hull[1]）、B = p6 = (-30, -94)（hull[4]）、C = p14 = (-61, 83)（hull[14]），dot = -5348。

「只 continue 跳过 b=A」的错代码输出 -5338，差 10——正是 b = h0 方向 ≈ +92.5° → b = h2 方向 ≈ -73°，方向断层 165° 让 c 跟丢了 c = h14。

正确修法

// 找 A 在 hull 上的位置 aPos (-1 = 不在 hull 上)
int aPos = -1;
for (int i = 0; i < H; ++i)
    if (A[a].id == convex[i].id) { aPos = i; break; }
int bStart = (aPos == -1) ? 0 : (aPos + 1) % H;
int bCnt   = (aPos == -1) ? H : H - 1;

// 初始 c 以 convex[bStart] 为 b 基准 (不是 convex[0]!)
int c = bStart;
ll tar = dot(A[a], convex[bStart], convex[c]);
for (int i = 0; i < H; ++i) {
    ll lans = dot(A[a], convex[bStart], convex[i]);
    if (lans < tar) { tar = lans; c = i; }
}

for (int t = 0; t < bCnt; ++t) {
    int b = (bStart + t) % H;
    auto check = [&]() {
        return dot(A[a], convex[b], convex[c % H]) >=
               dot(A[a], convex[b], convex[(c + 1) % H]);
    };
    while (check()) c++;
    ans = min(ans, (ll) dot(A[a], convex[b], convex[c % H]));
}

3 个改动：

1. bStart = (aPos + 1) % H：让 b 从真正的 CCW 起点开始

2. bCnt = H - 1：走 h-1 步绕回 A_prev 终止（A 自己天然跳过）

3. check 用 >= 而不是 >：dot 平台时推到末尾，避免 c 卡在平台前段让下一个 b 跟不上

「为什么 hull[0] 是幸运 case」

如果 A = h0（hull 最左下顶点），那 A_next = h1——代码从 b = h0 起扫，第一轮 b = A 直接被 continue 跳，第二轮 b = h1 恰好就是真正的 CCW 起点，方向断层不出现。这就是为什么「只 continue 跳过 b=A」的写法样例 1 过了（样例 1 hull 是矩形 + 内部点，所有 hull 顶点对称，A 在内部时根本没断层；A 在 hull 上时恰好都是 hull[0] 的对称 case，运气好）。

但样例不能覆盖「A 在 hull 上但不是 hull[0]」这种邪恶 case——test 44 就是用这个数据。

📎 动画与源码

下面 3 张截图（位于「附件」节）来自 astral_decay_demo.html 的关键帧。HTML 本体在附件节末尾（zip 包，解压后用浏览器打开 .html = 完整交互演示，含 4 个 mini-demo + 主算法 step-by-step）。

AC 代码

AC 提交链接（Codeforces Gym 105941） 见 vjudge submission 记录

完整 .cpp 含 700 行几何模板 + 50 行 Solve()。完整源码见附件 Astral_Decay.cpp.txt（下载后改回 .cpp）。下面只展开核心 Solve()：

展开 Solve() 函数核心（修正后版本）

void Solve() {
    ll N;
    cin >> N;
    vector<Point<ll>> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        A[i].id = i;
    }
    auto convex = make_convex_hull(A, true, HULL_FULL);
    ll H = SZ(convex);
    ll ans = 0;  // A=B=C 给 0, 安全下界
    for (int a = 0; a < N; ++a) {
        // 找 A[a] 在 hull 上的位置, b 起点设为 A_next
        int b = 0;
        for (int i = 0; i < H; ++i) {
            if (A[a].id == convex[i].id) {
                b = (i + 1) % H;
                break;
            }
        }
        // 初始化 c: 以 convex[b] 为 b 基准找最优 c
        int c = 0;
        do {
            ll tar = dot(A[a], convex[b % H], convex[c]);
            for (int i = 0; i < H; ++i) {
                ll lans = dot(A[a], convex[b % H], convex[i]);
                if (lans < tar) { c = i; tar = lans; }
            }
        } while (false);
        // 双指针扫 H 步 (A 在 hull 上时第 1 轮 b=A 被 continue 跳, 剩 H-1 轮)
        for (int i = 0; i < H; ++i) {
            if (A[a].id == convex[b % H].id) { ++b; continue; }
            auto check = [&]() {
                return dot(A[a], convex[b % H], convex[c % H]) >=
                       dot(A[a], convex[b % H], convex[(c + 1) % H]);
            };
            while (check()) c++;
            ans = min(ans, (ll) dot(A[a], convex[b % H], convex[c % H]));
            ++b;
        }
    }
    cout << ans << "\n";
}

心路历程（WA → AC）

按真实的 debug 过程列：

1. 第一版按题解写：枚举 A、b 沿 hull 走 h 步、c 双指针。样例 1 过，WA on test 44。

2. 加 if (A.id == convex[b].id) continue; 跳过 b = A 退化轮。样例 1 仍过，仍 WA on test 44。

3. cyaron 风格 stress test：本机 gen 17~30 点全在 hull 上的随机数据（椭圆采点 + 强制 h ≥ 5）+ brute O(n³) 对拍。第 204 次种子抓到 17 点反例。

4. 手算反例确认根因：A = p11 在 hull[1]（不是 hull[0]！），b 按 hull 顺序走方向不单调（+92.5° → -73° 回退 165°），c 单向推进跟不上。

5. 正确修法：b 起点改 (aPos + 1) % H、走 H-1 步；c 初始扫描以 convex[bStart] 为 b 基准（不再用 convex[0]）；check 改 >=。

6. AC。

关键 take-away

• 「光看样例 AC」≠「算法正确」——样例 1 的 hull 是对称矩形 + 1 内部点，所有特殊 case（A 在 hull 上非 hull[0]）都不触发；样例 2 是随机 10 点稀疏分布，也不触发。

• 「跳过 b=A」是表面修法，「b 起点改 A_next****」才是治本——前者样例过但 test 44 仍 WA，后者通过。

• 对拍 gen 要能触发「A 在 hull 顶点上但不是 hull[0]」：均匀随机点云通常 A 在 hull 上的概率 ≈ h/n 很低；必须强制让 hull 顶点占比 ≥ 50%。本会话用的 gen：椭圆采 h ≥ 5 点 + 调过 phi/asp 让 hull 形状非对称。

• 几何模板里的 gen_convex_polygon 当 N ≤ 2 必死循环（N=1: j=(0+1)%1=i 让 A[i] == A[j] 永真；N=2: k=(0+2)%2=i 让 cross 三点退化恒 0）。这次顺便发现 + 修了（加 N ≤ 2 退化分支撒不重点）。

附件

astral_decay_demo.html.zip

Astral_Decay.cpp.txt

官方题解 PDF (CCPC 河南省赛 2025 全题题解, 命题组 BUAA)