Znzryb's Blog
0%

POJ 3608 - Bridge Across Islands

Posted on

原题：POJ 3608 Bridge Across Islands（POJ 评测机太老仅 C++98，强烈推荐 vjudge 上的镜像 OpenJ_Bailian-3851）。本题是两凸多边形最近距离的旋转卡壳模板题，但有一个反直觉的「单调推进准则」选择 —— 第一版贪心在 OJ 上 TLE，调试改 cross 单调推进后又 WA，最终发现单次调用对偶覆盖不完整，必须 (A, B) 和 (B, A) 各跑一次。

题目大意

太平洋中央有一个王国，领土由两座岛屿组成，被洋流冲成两个凸多边形。国王要造一座桥连两岛，问两岛边界的最小距离是多少。

输入

多组测试用例。每组先给两整数 NN 和 MM ( 3≤N,M≤100003 \le N, M \le 10000 )，接下来 NN 行各给一对坐标描述第一个凸多边形的一个顶点（已按某种顺序给出，CW 或 CCW），再接 MM 行给第二个凸多边形顶点。坐标 ∈[−10000,10000]\in [-10000, 10000] 。

一行 N=M=0N = M = 0 表示输入结束。

输出

每组输出最小距离，误差 ≤10−3\le 10^{-3} 。

样例

1
2
3
4
5
6
7
8
9
10
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
1.00000

思路讲解

一句话

两凸多边形最近距离 = 旋转卡壳 + facing 弧双指针 O(N+M)O(N + M) ；推进准则用「cross(a, b') 角度差」、不要用「dis2 < dis1 顶点-边距离单峰」（贪心在背面弧会卡住）；最终结果必须 (A, B) 和 (B, A) 各调一次取 min⁡\min 才覆盖完整。

把最近距离归并到「顶点 → 线段」

两个不相交的凸多边形之间，最小距离的实现位置只有三种：

特征对 是否独立 备注
顶点 - 边内部 ✓ 主路径 从某顶点向另一多边形某条边作垂线，垂足落在边内
顶点 - 顶点 退化 当 dist(vA, seg(eB))\mathrm{dist}(v_A,\ \mathrm{seg}(e_B)) 的垂足落在 eBe_B 外，点-线段距离自动退成点-点距离
边 - 边 退化 仅当两边平行才可能；端点也取得到，被「顶点对线段」覆盖

关键不变量：枚举所有 (顶点, 对面边)(顶点,\ \mathrm{对面边}) 对，算点-线段距离取 min⁡\min ，三种情形一网打尽。

facing 弧 + 单调推进

固定 AA 上一个顶点 pp ，凸性下 BB 上「真正可能成为离 pp 最近的那条边」有且仅有一条 —— 称它为 pp 的 facing edge。形象点：从 pp 看过去， BB 朝向 pp 那半弧上正对 pp 的那条边，其它边要么被它挡住、要么转到背面去了。

把 pp 沿 AA 走 CCW 一圈，那条 facing 边在 BB 上的位置是**「短程单调、长程往返」**：

  • 短程（ pp 走在 AA 朝 BB 那半弧上）：facing 边在 BB 上 单调推进（不回退）

  • 长程（ pp 越过 AA 的背面弧）： BB 没有新边可选，facing 边只能沿同一段 facing 弧 退回来

  • 整圈轨迹 = 「推过去 → 退回来」 = 往返

算法直接好处：两个指针不需要走完一整圈，各自只走完自己的 facing 弧就够了，总步数 ≤N+M\le N + M 。

初始 facing pair：A 最低 + B 最高

按代码取：

  • eA\texttt{eA} = AA 上 yy 最小的点的下标

  • eB\texttt{eB} = BB 上 yy 最大的点的下标

几何上 eA\texttt{eA} 看上去就是 eB\texttt{eB} 、 eB\texttt{eB} 看下去就是 eA\texttt{eA} —— 这一对是初始 facing pair，也是 AA / BB 各自 facing 弧的一个端点。

不过这个初始只在「 BB 整体在 AA 上方」时直观对齐；其它分布下（ AA 在右、 BB 在左之类）yMnA + yMxB 不一定是真 facing pair。没关系 —— 推进准则用 cross 角度差驱动后，初始位置不正确也能在 O(N+M)O(N + M) 步内追上正确的对踵 pair，所以这个朴素初始化就够了。

cross(a, b') 推进准则（核心）

设：

  • a⃗=Ai+1−Ai\vec{a} = A_{i+1} - A_i ： AA 在 AiA_i 的 CCW 出边方向

  • b⃗′=Bj−Bj+1\vec{b}' = B_j - B_{j+1} ： BB 在 BjB_j 的 CCW 出边 反向（因为 BB 的 facing 弧逆 BB 的 CCW 序前进）

推进准则：

cross(a⃗, b⃗′){>0⇒ ++i （推进 A）<0⇒ ++j （推进 B）=0两个都试一下取 min\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 处 a⃗\vec{a} 和 b⃗′\vec{b}' 都大约朝 +x+x ，几乎平行同向；两者沿各自多边形 CCW 推进时都向 CCW 方向旋转（凸性）。 cross(a⃗, b⃗′)\mathrm{cross}(\vec{a},\ \vec{b}') 衡量两者角度差：

  • >0> 0 ： b⃗′\vec{b}' 在 a⃗\vec{a} 的 CCW 一侧 ⇒\Rightarrow a⃗\vec{a} 角度落后 ⇒\Rightarrow 让 AA 推一步追上

  • <0< 0 ：反之，让 BB 推一步

为什么这样不会 TLE：每步刚好推一个指针、各自只能 forward。 ii 走完 AA 一圈、 jj 走完 BB 一圈就停，总步数 ≤N+M\le N + M 。背面弧问题自动消失 —— cross 一直按角度差驱动，根本不依赖「dis 谁更小」这种局部贪心。

为什么必须 (A, B) + (B, A) 各调一次

单次 cal_min_dis_two_convex(A, B) 只覆盖**「 AA 顶点 → BB 边」**这组对偶配置 —— 也就是「枚举 AA 上每个顶点，找 BB 上对应的 facing 边」。

但反对称几何里答案可能取在另一边：细长 AA 戳向粗 BB 的边中间， AA 的端点垂足落在 BB 的边内部 —— 这种「 AA 顶点 - BB 边」抓得到；反过来「 BB 顶点 - AA 边」抓不到。

解决：把同一份代码以 (B, A) 参数顺序再跑一遍，补上反向对偶，最后两次取 min⁡\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));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



漏一次会在 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

DB cal_min_dis_two_convex(vector<Point> A, vector<Point> 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;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

完整源码（含几何模板、读入、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

mentor.tex 编译产物 PDF —— me/mentor 5 步推导对话录（题面 / 三类特征对 / facing 弧 / 旋转卡壳骨架 / cross 推进准则）

Bridge_Across_Islands.cpp.txt