POJ 3608 - Bridge Across Islands · znzryb
原题:[POJ 3608 Bridge Across Islands](http://poj.org/problem?id=3608)(POJ 评测机太老仅 C++98,强烈推荐 vjudge 上的镜像 [OpenJ\_Bailian-3851](https://vjudge.net/problem/OpenJ_Bailian-3851))。本题是两凸多边形最近距离的旋转卡壳模板题,但有一个反直觉的「**单调推进准则**」选择 —— 第一版贪心在 OJ 上 TLE,调试改 `cross` 单调推进后又 WA,最终发现单次调用对偶覆盖不完整,必须 `(A, B)` 和 `(B, A)` 各跑一次。
# 题目大意
太平洋中央有一个王国,领土由两座岛屿组成,被洋流冲成两个凸多边形。国王要造一座桥连两岛,问两岛边界的最小距离是多少。
## 输入
多组测试用例。每组先给两整数 $N$ 和 $M$ ( $3 \le N, M \le 10000$ ),接下来 $N$ 行各给一对坐标描述第一个凸多边形的一个顶点(**已按某种顺序**给出,CW 或 CCW),再接 $M$ 行给第二个凸多边形顶点。坐标 $\in [-10000, 10000]$ 。
一行 $N = M = 0$ 表示输入结束。
## 输出
每组输出最小距离,误差 $\le 10^{-3}$ 。
## 样例
```
4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0
```
输出:
```
1.00000
```
# 思路讲解
## 一句话
两凸多边形最近距离 = **旋转卡壳 + facing 弧双指针** $O(N + M)$ ;推进准则用「**`cross(a, b')` 角度差**」、不要用「`dis2 < dis1` 顶点-边距离单峰」(贪心在背面弧会卡住);最终结果必须 `(A, B)` 和 `(B, A)` 各调一次取 $\min$ 才覆盖完整。
## 把最近距离归并到「顶点 → 线段」
两个**不相交**的凸多边形之间,最小距离的实现位置只有三种:
| 特征对 | 是否独立 | 备注 |
| --- | --- | --- |
| **顶点 - 边内部** | ✓ 主路径 | 从某顶点向另一多边形某条边作垂线,垂足落在边内 |
| **顶点 - 顶点** | 退化 | 当 $\mathrm{dist}(v_A,\ \mathrm{seg}(e_B))$ 的垂足落在 $e_B$ 外,点-线段距离自动退成点-点距离 |
| **边 - 边** | 退化 | 仅当两边平行才可能;端点也取得到,被「顶点对线段」覆盖 |
> **关键不变量**:枚举所有 $(顶点,\ \mathrm{对面边})$ 对,算**点-线段距离**取 $\min$ ,三种情形一网打尽。
## facing 弧 + 单调推进
固定 $A$ 上一个顶点 $p$ ,凸性下 $B$ 上「真正可能成为离 $p$ 最近的那条边」**有且仅有一条** —— 称它为 $p$ 的 **facing edge**。形象点:从 $p$ 看过去, $B$ 朝向 $p$ 那半弧上正对 $p$ 的那条边,其它边要么被它挡住、要么转到背面去了。
把 $p$ 沿 $A$ 走 CCW 一圈,那条 facing 边在 $B$ 上的位置是**「短程单调、长程往返」**:
- **短程**( $p$ 走在 $A$ 朝 $B$ 那半弧上):facing 边在 $B$ 上 **单调推进**(不回退)
- **长程**( $p$ 越过 $A$ 的背面弧): $B$ 没有新边可选,facing 边只能沿同一段 facing 弧 **退回来**
- 整圈轨迹 = 「推过去 → 退回来」 = **往返**
**算法直接好处**:两个指针不需要走完一整圈,**各自只走完自己的 facing 弧就够了**,总步数 $\le N + M$ 。
## 初始 facing pair:A 最低 + B 最高
按代码取:
- $\texttt{eA}$ = $A$ 上 $y$ 最小的点的下标
- $\texttt{eB}$ = $B$ 上 $y$ 最大的点的下标
几何上 $\texttt{eA}$ 看上去就是 $\texttt{eB}$ 、 $\texttt{eB}$ 看下去就是 $\texttt{eA}$ —— 这一对是初始 facing pair,也是 $A$ / $B$ 各自 facing 弧的一个端点。
不过这个初始**只在「 $B$ 整体在 $A$ 上方」时直观对齐**;其它分布下( $A$ 在右、 $B$ 在左之类)`yMnA + yMxB` 不一定是真 facing pair。**没关系** —— 推进准则用 `cross` 角度差驱动后,初始位置不正确也能在 $O(N + M)$ 步内追上正确的对踵 pair,所以这个朴素初始化就够了。
## `cross(a, b')` 推进准则(核心)
设:
- $\vec{a} = A_{i+1} - A_i$ : $A$ 在 $A_i$ 的 **CCW 出边方向**
- $\vec{b}' = B_j - B_{j+1}$ : $B$ 在 $B_j$ 的 CCW 出边 **反向**(因为 $B$ 的 facing 弧逆 $B$ 的 CCW 序前进)
**推进准则**:
$$
\mathrm{cross}(\vec{a},\ \vec{b}') \quad
\begin{cases}
> 0 & \Rightarrow\ \mathtt{++i}\ \text{(推进 A)} \\
< 0 & \Rightarrow\ \mathtt{++j}\ \text{(推进 B)} \\
= 0 & \text{两个都试一下取 min}
\end{cases}
$$
**几何意义**:初始 facing pair 处 $\vec{a}$ 和 $\vec{b}'$ 都大约朝 $+x$ ,几乎平行同向;两者沿各自多边形 CCW 推进时**都向 CCW 方向旋转**(凸性)。 $\mathrm{cross}(\vec{a},\ \vec{b}')$ 衡量两者角度差:
- $> 0$ : $\vec{b}'$ 在 $\vec{a}$ 的 CCW 一侧 $\Rightarrow$ $\vec{a}$ 角度**落后** $\Rightarrow$ 让 $A$ 推一步追上
- $< 0$ :反之,让 $B$ 推一步
> **为什么这样不会 TLE**:每步刚好推一个指针、各自只能 forward。 $i$ 走完 $A$ 一圈、 $j$ 走完 $B$ 一圈就停,总步数 $\le N + M$ 。背面弧问题自动消失 —— `cross` 一直按角度差驱动,根本不依赖「dis 谁更小」这种局部贪心。
## 为什么必须 `(A, B)` + `(B, A)` 各调一次
单次 `cal_min_dis_two_convex(A, B)` 只覆盖**「 $A$ 顶点 → $B$ 边」**这组对偶配置 —— 也就是「枚举 $A$ 上每个顶点,找 $B$ 上对应的 facing 边」。
但反对称几何里答案可能取在另一边:细长 $A$ 戳向粗 $B$ 的边中间, $A$ 的端点垂足落在 $B$ 的边内部 —— 这种「 $A$ 顶点 - $B$ 边」抓得到;反过来「 **$B$ 顶点 - $A$ 边**」抓不到。
**解决**:把同一份代码以 `(B, A)` 参数顺序再跑一遍,补上反向对偶,最后两次取 $\min$ :
`c++
DB ans = INFINITY;
ans = min(ans, cal_min_dis_two_convex(A, B));
ans = min(ans, cal_min_dis_two_convex(B, A));
```
漏一次会在 stress test 第 24 个 seed 翻车(**已实测**,反例见 `counterexample_seed24.html` 附件,期望 $62.29$ 实测 $63.7$ )。
## 📎 动画与源码
- $\vec{a}$ / $\vec{b}'$ 向量 + `cross` 推进逐步演示:`cross_product_demo.html`(见附件)
- 单次调用对偶不完整反例:`counterexample_one_call_only.html`、`counterexample_seed24.html`
# AC 代码
[**AC 提交链接(vjudge OpenJ\_Bailian-3851)**](https://vjudge.net/solution/69793877)
核心函数:
```
// 两凸多边形最近距离(旋转卡壳, O(n + m))
// 单次调用只覆盖「A 边 → B 顶点」配置,
// 调用方需以 (A, B) 和 (B, A) 各调一次取 min。
template<class T>
DB cal_min_dis_two_convex(vector<Point<T>> A, vector<Point<T>> B) {
reorder_polygon(A);
reorder_polygon(B);
ll yMnA = min_element(all(A), [](const Point<T> &a, const Point<T> &b) {
return a.y < b.y;
}) - A.begin();
ll yMxB = max_element(all(B), [](const Point<T> &a, const Point<T> &b) {
return a.y < b.y;
}) - B.begin();
DB ans = INFINITY;
ll eA = yMnA, eB = yMxB;
for (int _ = 0; _ < SZ(A) + SZ(B); ++_) {
auto check = [&]() {
auto vecA = A[(eA + 1) % SZ(A)] - A[eA];
auto vecB = B[(eB + 1) % SZ(B)] - B[eB];
return cross(vecA, vecB) > 0;
};
while (check()) ++eB, eB %= SZ(B);
ans = min(ans, distanceSS(Line(A[(eA + 1) % SZ(A)], A[eA]),
Line(B[(eB + 1) % SZ(B)], B[eB])));
eA = (eA + 1) % SZ(A);
}
return ans;
}
```
完整源码(含几何模板、读入、Solve 框架):
<details>
<summary>展开完整 C++ 源码(Bridge_Across_Islands.cpp)</summary>
完整源码 ~840 行较长,含整套几何模板(`Point` / `Line` / `cross` / `distanceSS` / `reorder_polygon` 等)+ `cal_min_dis_two_convex` + 多组数据 main。直接下载页面末尾附件 `Bridge_Across_Islands.cpp.txt`(去掉 `.txt` 后缀即为 `.cpp`)。
</details>
# 心路历程(TLE → WA → AC)
1. **第一版 TLE**:用「`dis2 < dis1` 顶点-边距离贪心」推进 —— 在 $A$ 朝 $B$ 那半弧上确实单调,但当 $i$ 越过 $A$ 的背面弧后单调性破裂, $j$ 想往回走但只能 forward,**陷在 $B$ 上转圈**,OJ 测出 TLE。
2. **第二版 WA**:换成 `cross(a, b')` 角度判定,单次 `cal_min_dis_two_convex(A, B)` 调用 —— 本地 cyaron stress 用近圆形测 5000 case 全过、提交 OJ WA。`cyaron-stress` skill 警告过:**cyaron `Polygon.convex_hull` 默认近圆形是对拍盲区**,必须主动用 ellipse / spiked / heart / lemon 等曲率非均匀形状才能触发反例。换成椭圆 + spike 形状后,stress seed 24 立刻给出 `yMnA + yMxB` 配对失效的反例(见附件 `counterexample_seed24.html`)。
3. **第三版 AC**:加上 `(B, A)` 反向调用取 $\min$ 补对偶。
\textcolor{red}{**收获心法**}:
- 旋转卡壳推进准则用 **`cross` 角度差** 而不是 **dis 单峰**。「dis 单峰」是教材级 fact 但只在曲率均匀分布下成立。
- 单次调用对偶不完整 —— 看 mentor.tex 里 me/mentor 第 3 步对话录有详细推导,需要 `(A, B)` + `(B, A)` 反向。
- 对拍**必须**用非均匀曲率形状(椭圆 / spike / heart / lemon)破盲区;cyaron `Polygon.convex_hull` 默认值就是盲区本身。
# 附件
```
[Bridge_Across_Islands_html_demos.zip](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/a5d4f23d-b0e0-4e2c-bb98-8f549c1b192e/Bridge_Across_Islands_html_demos.zip?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB46642EKW65W%2F20260511%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260511T130045Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEE0aCXVzLXdlc3QtMiJIMEYCIQDJZo2BlMDllhRcotSqIs3wpg3zFvnPSttupaKahd2HrAIhAP8BzQtP8sA470xXAe2uebA3YL2X0BvtHrqGJlZJQxXOKv8DCBUQABoMNjM3NDIzMTgzODA1IgzZQqsLJmLGj9qQ4Wgq3AN7SLQ9DF7lrBxwYIK2mnrcicnOyEF9JllTpBCC%2FLCz2oRz%2F6y34rYC0D233gVrL4I1aXE8XY0viNn1VG0u4nihpEfB6x7WzcpNG6TFXIeuLzK%2Bhb917RkloKQrf%2FLAFUHAGkaB9BcUw2zNg22mJHdF9bBSbKfh%2BZnh3%2F0wT%2FShC6LBCCYi94yWxGVHbzmHpg%2BsoZqRkeZ0p%2BaL26Phpnrbr7i2tFc3rRLK%2B7%2Byc13hREXOiJh%2BYEo4MbZMdtkuUwHeDSyHQq11xTpbAxmwU9V1lM1P9jLLJtCIxz%2FOSIprdn23bCaOe%2BfM9zotz0Hrsu0fimTUQbXGas7HM51Oj8BabCJbzPzYF4hf%2FubhHDbgEDtNhRmlJPKDzLYhdl0h3VCpb3rizYZTHZpPoDo2CZt6oitPvr0kgzkytB%2FCi4i%2FtuK%2B%2FRhWijkQEdWWFJ7gBec%2FQP2mT5jHEDc6hzQNb0ajWow7%2FehpFShQtRDYxV0sh2sABND1swndymqQ9mE4975PIKrLCExh9iOM33UJsPO86qjQBzgKr%2B3QC6Wuf1UXwvpUrrP6ZQvM2uw7QfPuGo7n%2BN4Mku2XnioGIv1fdiYd8%2Bnu6hgnx90MjvADDCa6Wb6slu0DJF2rA2sVKjCykofQBjqkAQ8I8LQP%2F7BQLZ5Gle4347gX1EPXaf85KfLNjmfq8hVXSY6QWMSY4x72K5mQQdHfImIfMWTGQaSJ%2FCmfrBdhWQhUK5Ztifi8YbghVXofM71Kvk4WJupdQWz0AdSluIgbm%2Flp3FSRGQlUirKO6bTjXBpjspGeV0RRt4sFNgHShQLuoPibgylGHvucQuGKSqpURB5ea8vVIzVeYME%2FuJWREQ7OESwN&X-Amz-Signature=880d22a78cbc6375a953ef56d0d05ad245e4ad7a8752743525ac72ee7789da0e&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
[mentor.tex 编译产物 PDF —— me/mentor 5 步推导对话录(题面 / 三类特征对 / facing 弧 / 旋转卡壳骨架 / cross 推进准则)](https://media.znzryb.com/20260511-1f95fd1f/Bridge_Across_Islands_mentor_4a8099a3.pdf)
[Bridge_Across_Islands.cpp.txt](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/52f21696-ed60-4b0b-a7aa-6e11d7e133c2/Bridge_Across_Islands.cpp.txt?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB46642EKW65W%2F20260511%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260511T130045Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEE0aCXVzLXdlc3QtMiJIMEYCIQDJZo2BlMDllhRcotSqIs3wpg3zFvnPSttupaKahd2HrAIhAP8BzQtP8sA470xXAe2uebA3YL2X0BvtHrqGJlZJQxXOKv8DCBUQABoMNjM3NDIzMTgzODA1IgzZQqsLJmLGj9qQ4Wgq3AN7SLQ9DF7lrBxwYIK2mnrcicnOyEF9JllTpBCC%2FLCz2oRz%2F6y34rYC0D233gVrL4I1aXE8XY0viNn1VG0u4nihpEfB6x7WzcpNG6TFXIeuLzK%2Bhb917RkloKQrf%2FLAFUHAGkaB9BcUw2zNg22mJHdF9bBSbKfh%2BZnh3%2F0wT%2FShC6LBCCYi94yWxGVHbzmHpg%2BsoZqRkeZ0p%2BaL26Phpnrbr7i2tFc3rRLK%2B7%2Byc13hREXOiJh%2BYEo4MbZMdtkuUwHeDSyHQq11xTpbAxmwU9V1lM1P9jLLJtCIxz%2FOSIprdn23bCaOe%2BfM9zotz0Hrsu0fimTUQbXGas7HM51Oj8BabCJbzPzYF4hf%2FubhHDbgEDtNhRmlJPKDzLYhdl0h3VCpb3rizYZTHZpPoDo2CZt6oitPvr0kgzkytB%2FCi4i%2FtuK%2B%2FRhWijkQEdWWFJ7gBec%2FQP2mT5jHEDc6hzQNb0ajWow7%2FehpFShQtRDYxV0sh2sABND1swndymqQ9mE4975PIKrLCExh9iOM33UJsPO86qjQBzgKr%2B3QC6Wuf1UXwvpUrrP6ZQvM2uw7QfPuGo7n%2BN4Mku2XnioGIv1fdiYd8%2Bnu6hgnx90MjvADDCa6Wb6slu0DJF2rA2sVKjCykofQBjqkAQ8I8LQP%2F7BQLZ5Gle4347gX1EPXaf85KfLNjmfq8hVXSY6QWMSY4x72K5mQQdHfImIfMWTGQaSJ%2FCmfrBdhWQhUK5Ztifi8YbghVXofM71Kvk4WJupdQWz0AdSluIgbm%2Flp3FSRGQlUirKO6bTjXBpjspGeV0RRt4sFNgHShQLuoPibgylGHvucQuGKSqpURB5ea8vVIzVeYME%2FuJWREQ7OESwN&X-Amz-Signature=2e7c0355d4d1a5ebedf4f1cf364976f6af2eaa515ee3a44baa5fd8d304ca2563&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)