CCPC 河南 2025 L - Astral Decay · znzryb
[**vjudge 链接**](https://vjudge.net/problem/Gym-105941L) · [**Codeforces Gym 原题**](https://codeforces.com/gym/105941/problem/L) · 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
```javascript
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 点,本会话抓到)
```javascript
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。
### 正确修法
```cpp
// 找 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 起点开始
1. `bCnt = H - 1`:走 h-1 步绕回 `A_prev` 终止(A 自己天然跳过)
1. **`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)**](https://codeforces.com/gym/105941/problem/L) 见 vjudge submission 记录
完整 .cpp 含 700 行几何模板 + 50 行 Solve()。**完整源码见附件** **`Astral_Decay.cpp.txt`**(下载后改回 `.cpp`)。下面只展开核心 Solve():
::: 展开 Solve\(\) 函数核心(修正后版本)
```cpp
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**。
1. **加** **`if (A.id == convex[b].id) continue;`** **跳过 b = A 退化轮**。**样例 1 仍过,仍 WA on test 44**。
1. **cyaron 风格 stress test**:本机 gen 17~30 点全在 hull 上的随机数据(椭圆采点 + 强制 h ≥ 5)+ brute O(n³) 对拍。**第 204 次种子抓到 17 点反例**。
1. **手算反例确认根因**:A = p11 在 hull[1](**不是 hull[0]**!),b 按 hull 顺序走方向不单调(+92.5° → -73° 回退 165°),c 单向推进跟不上。
1. **正确修法**:b 起点改 `(aPos + 1) % H`、走 H-1 步;c 初始扫描以 `convex[bStart]` 为 b 基准(不再用 `convex[0]`);`check` 改 `>=`。
1. **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](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/7a32f9af-e2d3-4362-9cac-ca3bef34bb23/astral_decay_demo.html.zip?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB46633OXOBMU%2F20260516%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260516T044934Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEL3%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLXdlc3QtMiJHMEUCIErayXmaFK%2B19LgRDTrvoEZV11Y04jMX%2B71ReI%2BjJNajAiEAjGxUAGyivyFCBaeXeQsSggM4pWeSApyeXDXLrxJ5TE0qiAQIhv%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FARAAGgw2Mzc0MjMxODM4MDUiDA%2BeQ8bMGq99V2f18yrcA3bI2c7LRvwYYI0yIhjWHP8qwXtVnfAiIfrPVjKdU6lbRimdGZgMS0YVfLooaSAMFn9QsJ8uJLSRuua6RHbjeWFm%2F4ZpzMi2ZpPc58QGDY3lDA5cZJAqJAjWraYfkbSybJp5EZ2h%2BQj%2FshLaiOhImRZriiychqEmPmaZjIWl0emBiLY%2F8WWQvad8ACUvOKAzYbM0L0DgQw7n6gtS38y%2FZg9ZfwXz%2FMRUNCVcttKWMdnFEdFGs5FLbGBcIXrlHN%2F2Xp5KTlU8hm0Qm4f02lNJjRq7B7BWAh%2FM2fFknIDy8EOtkq7SfAxi9EZKiHhqRGIClWC6ZUWpdTXe3fDWZOgxNGOpdCnhMvyw%2FkeDoH8fFs9ZCd43xSrWLPanZYVmvg%2FebCxtmdx%2FCxICwNxC85S7T5gIIB6oJ5E%2BqM5aaTkWoZ8WJCQytnBN7s1wER%2FiIQWJLHiwyzFlQecYJemBpQ4cApccyMm7c2h8Y04%2FeY8iHyoMTQGVSccvJlNxwfBb9hwg6pKTEwdhq%2BSh4DwsWiFgpGxjOlUKfEuQBglbTxzEHhkKKsSTzOLzPeo0Kb6PwRDa4APOteVm5KM2Qnf7i%2BR10dbCiSNa%2BpjRlI3EKkoYmh%2BZmkzvXQi1AOGrzosvMNnln9AGOqUB9gfswoai%2Fpwz72geibwyvqw3NOkSUDQQqZO9k6ru0QVcZGbW%2F%2F5Bm5tCSbkluArJS8ivD%2Fdnh7yE1z%2BX8WQ8l40M7PTKy1zqm4WY015G%2BFTB2FZui0BDXZk7OwQp%2Fc%2BITmlSVO4wAhJ1QsFMwCbk4VlOsk%2B3UIDCySnu3J%2BMLE7mI%2BTLiedrmnMtqe%2F0Fdp6VnM9L4gE5E3K%2BQZcD19gpxe%2BP7Oa&X-Amz-Signature=2571e68bf61641bf799a3a0bfa0ae2b44320c09b88ba631d0d925ea32f952a08&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
[Astral_Decay.cpp.txt](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/f5a811e3-364f-478b-b179-470ea4366798/Astral_Decay.cpp.txt?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB46633OXOBMU%2F20260516%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260516T044934Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEL3%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLXdlc3QtMiJHMEUCIErayXmaFK%2B19LgRDTrvoEZV11Y04jMX%2B71ReI%2BjJNajAiEAjGxUAGyivyFCBaeXeQsSggM4pWeSApyeXDXLrxJ5TE0qiAQIhv%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FARAAGgw2Mzc0MjMxODM4MDUiDA%2BeQ8bMGq99V2f18yrcA3bI2c7LRvwYYI0yIhjWHP8qwXtVnfAiIfrPVjKdU6lbRimdGZgMS0YVfLooaSAMFn9QsJ8uJLSRuua6RHbjeWFm%2F4ZpzMi2ZpPc58QGDY3lDA5cZJAqJAjWraYfkbSybJp5EZ2h%2BQj%2FshLaiOhImRZriiychqEmPmaZjIWl0emBiLY%2F8WWQvad8ACUvOKAzYbM0L0DgQw7n6gtS38y%2FZg9ZfwXz%2FMRUNCVcttKWMdnFEdFGs5FLbGBcIXrlHN%2F2Xp5KTlU8hm0Qm4f02lNJjRq7B7BWAh%2FM2fFknIDy8EOtkq7SfAxi9EZKiHhqRGIClWC6ZUWpdTXe3fDWZOgxNGOpdCnhMvyw%2FkeDoH8fFs9ZCd43xSrWLPanZYVmvg%2FebCxtmdx%2FCxICwNxC85S7T5gIIB6oJ5E%2BqM5aaTkWoZ8WJCQytnBN7s1wER%2FiIQWJLHiwyzFlQecYJemBpQ4cApccyMm7c2h8Y04%2FeY8iHyoMTQGVSccvJlNxwfBb9hwg6pKTEwdhq%2BSh4DwsWiFgpGxjOlUKfEuQBglbTxzEHhkKKsSTzOLzPeo0Kb6PwRDa4APOteVm5KM2Qnf7i%2BR10dbCiSNa%2BpjRlI3EKkoYmh%2BZmkzvXQi1AOGrzosvMNnln9AGOqUB9gfswoai%2Fpwz72geibwyvqw3NOkSUDQQqZO9k6ru0QVcZGbW%2F%2F5Bm5tCSbkluArJS8ivD%2Fdnh7yE1z%2BX8WQ8l40M7PTKy1zqm4WY015G%2BFTB2FZui0BDXZk7OwQp%2Fc%2BITmlSVO4wAhJ1QsFMwCbk4VlOsk%2B3UIDCySnu3J%2BMLE7mI%2BTLiedrmnMtqe%2F0Fdp6VnM9L4gE5E3K%2BQZcD19gpxe%2BP7Oa&X-Amz-Signature=6c1c2aeb9250ee1105a2552b4ecfa2c9cd6b889f5dcf2765b745c5c1bb9250ce&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
[官方题解 PDF (CCPC 河南省赛 2025 全题题解, 命题组 BUAA)](https://media.znzryb.com/20260516-cba4c1f6/CCPC_Henan_2025_sol_ccd60084.pdf)