官方题解只能做到 $O(n^3)$？玩的太差了。可以降到确定性的 $O(n)$ 时间、$O(n)$ 空间。关键是：把目标压成一条可见性窗口，用稀疏水平分解在线性时间内完成三角剖分，再用两条最短路围出的漏斗求到整条窗口的最短距离。下面把这几部分全部展开。
复杂度按标准几何 RAM 模型计算：坐标上的基本运算、方向判断和距离计算耗时 $O(1)$。设房间为有 $n$ 个顶点的简单多边形 $P$，守卫和雕塑的位置分别为严格位于 $P$ 内部的 $g,s$，$d_P(x,y)$ 表示限制在 $P$ 内的欧氏最短路长度。
把可见区域压成一条窗口
定义 $V(s)=\{x\in P:[s,x]\subseteq P\}$，并令 $R(s)=\overline{\operatorname{int}V(s)}$，即正则化可见区域。本题要求看见无穷小雕塑的至少一半，因此目标是 $R(s)$。一条视线若在若干墙角处分别受到两侧限制，就可能只剩一根没有宽度的可见线段；它看得见中心，却看不见半个雕塑。若所有接触墙角都允许视线向同一侧微转，该侧的一个小角区间便畅通，雕塑对应的一半可见；若两侧分别被阻挡，就只剩中心方向。取内部再取闭包，恰好删除后一种针状部分，并保留前一种边界位置。
先说明得到三角剖分后怎样在线性时间内求 $R(s)$。三角形之间以公共对角线相邻，其对偶图是一棵树。以包含 $s$ 的三角形为根，沿树向外遍历。进入一个三角形时，已经知道入口边上的可见区间 $I$；这个三角形内的可见部分就是三角形与以 $s$ 为顶点、以 $I$ 为底的角锥的交。用角锥的两条边界射线裁剪另外两条边，得到传给两个孩子的入口区间。
这个转移是精确的。连接 $s$ 与孩子三角形内一点的线段必须经过父子公共边；它的交点属于 $I$，当且仅当线段到入口以前都在 $P$ 内。入口以后的部分位于一个凸三角形中。因此，按对偶树深度归纳，每次传递的区间都恰好是对应边的可见部分。每个三角形只有一个父亲，每次只做常数次裁剪，总费用为 $O(n)$。
角宽为零的分支不产生二维可见区域。保留其余可见片，再取闭包，即得到 $R(s)$。两片在公共对角线上的重合区间按边的编号抵消，剩余有向边首尾连接，便得到可见区域的边界。每个三角形贡献常数条边，这一步也为 $O(n)$。若 $s$ 在公共对角线上，就把所有包含 $s$ 的三角形一起作为初始区域。这些三角形在对偶树中连通：连接两者的每道门都把房间分成两部分，两侧同时包含 $s$ 时，$s$ 必在门上。收缩这棵初始子树后，仍可按同样方式遍历。
若 $g\in R(s)$，答案为 $0$。否则，$R(s)$ 的边界中位于房间内部的线段称为窗口。每条窗口 $w=[a,b]$ 都与 $s$ 共线，并和一段原多边形边界围出一个不可见的口袋。径向边界经过中间墙角时，在接触点处分开；与墙重合的部分不作为窗口。
窗口为什么能完全隔开一个口袋？首先，$w$ 是简单多边形的一条内部弦，所以它把 $P$ 分成两部分。其次，从 $s$ 发出的另一条射线不可能穿过 $w$ 进入背后的部分：两条不同直线至多相交一次，而它们已经在 $s$ 相交。故窗口背后没有二维可见区域。不同口袋的内部不相交，包含 $g$ 的口袋只有一个通向 $R(s)$ 的窗口。
任意从 $g$ 到 $R(s)$ 的路径都必须先经过这条窗口，而窗口自身属于 $R(s)$。截取路径第一次到达窗口以前的部分，立即得到
$$ \min_{x\in R(s)}d_P(g,x)=\min_{x\in[a,b]}d_P(g,x). $$
选出这个窗口也只需线性时间。每个可见边界端点保留它在原多边形边上的位置；窗口两端对应的原边界区间就是口袋的边界。沿这些互不重叠的区间扫描并做点包含判断，总共只访问 $O(n)$ 个边界元素。
接下来需要解决的是：怎样在 $O(n)$ 时间内得到三角剖分，以及怎样求到整条线段的最短路。
用稀疏水平分解压缩原始边界
下面展开 Chazelle 线性三角剖分中的稀疏分解。删去多边形的一条边，得到一条简单折线。对任意含 $m$ 条边的连续子折线 $C$，把它看成一条无穷细的带，分别保留两侧边界。于是同一个几何点可以对应不同的边界位置，沿双侧边界一共有 $2m$ 个原始边的出现位置。
取扫描高度 $h(p)=p_y+\varepsilon p_x$，其中 $\varepsilon>0$ 为无穷小量，使不同原始顶点的高度互异。以下水平指 $h$ 的等值线。从顶点向左右作水平视线，遇到边界即停止。这些视线称为出口。无穷远处的两段水平射线接成一个出口；局部极值处保留对应的零长端口。只保留部分出口，得到一个水平可见性子图。每个区域的边界由出口和双侧边界上的弧交替组成；区域度数是出口数，也是弧数。只以出口连接相邻区域，得到的对偶图是一棵树。
一条弧的权重是它经过的原始边数，区域权重取各弧权重的最大值。我们维护两项性质：每个区域度数至多为 $4$；每条弧的权重至多为参数 $\gamma$。前者称为保形性。
还要尽可能删除出口。若出口一侧区域的度数至多为 $2$，且合并两个区域后每条弧的权重仍不超过 $\gamma$，就删除它。合并后的度数为 $d_1+d_2-2\le4$，所以保形性仍成立。用队列保存可删除出口，每次删除只更新常数个相邻位置，费用与处理的子图大小成正比。无法继续删除时，称所得子图具有粒度 $\gamma$。
稀疏性引理。 含 $m$ 条原始边的子折线，其保形、粒度为 $\gamma$ 的子图只有 $O(m/\gamma+1)$ 个区域和出口。
证明的关键是把不能删除的出口记到原始边界上。树中度数至多为 $2$ 的结点至少占一半，因此有线性多个出口邻接这样的区域。一个出口不能删除，只能是某条合并弧的权重将超过 $\gamma$，故这条弧包含至少 $\gamma$ 次相邻原始边之间的过渡。把该出口记到这些过渡上。
记账重数为常数：一条旧弧只可能参与删除其两端出口的操作；位于旧出口端点处的过渡，只在删除该出口时进入合并弧内部。双侧边界总共只有 $O(m)$ 次原始过渡，故出口数乘以 $\gamma$ 为 $O(m)$。这里用原始边之间的过渡计数，便不会重复计算被许多出口截开的同一条原始边。
弧只保存原折线上的起止位置，不复制中间顶点。一个含 $\gamma$ 条原始边的弧，在子图中仍只占 $O(1)$ 空间。后面的全部加速都建立在这个表示上。
射线查询、子图合并与保形性恢复
先给一个有 $k$ 个区域的稀疏子图建立射线查询结构。除了跨出口的邻接，再加入跨原始折线的邻接：同一段原始折线的两侧属于两个区域，就把它们相连。沿原边界合并两侧已有的分割位置，即可列出这些邻接；没有出口的长弧可以整段跳过。去掉自环、合并平行边后，得到一个规模为 $O(k)$ 的平面图。
需要把这个图划成小块。对一个有 $k$ 个结点的连通部分做 BFS，取上下两侧结点数都不超过 $k/2$ 的中位层。在它上下各 $\lceil\sqrt{k}\rceil$ 层中选最小的一层，得到总大小为 $O(\sqrt{k})$ 的两层。层数不足时使用根层或空层。删除它们以后，只需继续分割中间的带状部分；带外的连通部分已经不超过 $k/2$。
将带下方收缩成根，删除带上方。带内到根的距离为 $O(\sqrt{k})$。在每个面内加入一个零权结点并连向该面的边界，将所有面三角化。重新取一棵从根出发的 BFS 树，其深度仍为 $O(\sqrt{k})$；与树边互补的对偶边组成另一棵树。把每个原结点的单位权重放到一个关联三角形上，在这棵对偶树中找加权重心面。
取重心面三个顶点到根的树路径，便得到 $O(\sqrt{k})$ 个分隔结点。删去这些路径后，每个剩余部分对应重心面删除后的一个对偶树分支，权重至多为总权重的一半。不同分支间的平面路径必穿过所选树路径，所以这个划分同时具有连通性和大小保证。这给出了所需的平面分隔集构造。
递归分割，直到每块至多含 $r=k^{2/3}$ 个结点，记所有分隔结点的并为 $D$。规模为 $u$ 的递归结点产生 $O(\sqrt{u})$ 个分隔结点，平均每个原结点承担 $O(u^{-1/2})$。沿递归路径，$u$ 按固定比例下降，并在 $u\le r$ 时停止，故每个原结点总共承担 $O(r^{-1/2})$，从而 $|D|=O(k/\sqrt r)=O(k^{2/3})$。
查询一条水平射线时，先扫描 $D$ 中区域的全部原始边界弧，找到最近交点 $b$。若存在 $b$，继续扫描到达 $b$ 前的区域所在的剩余连通块；若不存在，则在有序的无穷远出口高度中二分，定位射线远端所在的区域。端点重合时保留常数个相邻区域。
设真正的最近交点为 $a$。如果 $a$ 尚未被找到，那么从 $a$ 到 $b$ 以前经过的区域都不属于 $D$：进入一个分隔区域必须穿过它的原始边界弧，从而产生比 $b$ 更近的已扫描交点。水平射线不会横穿另一条不同高度的水平出口。因此 $a$ 与 $b$ 前的区域属于同一个剩余连通块；无 $b$ 时同理延伸到远端。一次查询只扫描 $O(k^{2/3})$ 个区域，每个区域最多有 $4$ 条权重为 $\gamma$ 的弧，费用为 $O(\gamma k^{2/3}+\log(k+1))$。最后的对数项用于定位交点所在弧及其两侧区域。
取规范子折线长度 $m=2^j$，粒度为 $\gamma=2^{\lfloor j/5\rfloor}=\Theta(m^{1/5})$。由稀疏性，$k=O(m^{4/5})$，一次查询耗时 $f(m)=O(m^{11/15})$。任意长度为 $t$ 的连续区间可拆成每种长度至多两个二进制规范块，再加两端的残边。因为 $\sum_{i\le\log_2t}2^{11i/15}=O(t^{11/15})$，查询整个区间仍只需 $f(t)=O(t^{11/15})$。
现在合并两条相邻子折线 $C_1,C_2$ 的子图。沿 $C_1$ 的双侧边界单向扫描旧出口端点，维护当前位置 $p$ 以及视线在 $C_2$ 子图中经过的区域 $F$。连接点提供初始位置；若当前仍看见 $C_1$，便沿旧出口跳过它挡住的边界部分。进入相互可见的部分后，只处理两类事件。
第一类是下一个旧端点位于 $F$ 中，且它在 $F$ 内的射线先到达 $C_2$ 的原始边界，再可能到达旧配对端点。此时插入新的跨子折线出口，推进 $p$。第二类是 $F$ 的某条出口端点看见了当前源弧上尚未处理的位置。检查 $F$ 的常数个出口端点，在所有合法命中中取沿源边界最靠后的位置，推进到那里，并按源边界在该点之后进入的那一侧更新 $F$。每个候选只需射线查询和边界次序比较，查询对象限于 $F$ 和当前源区域的常数条弧，每条长度为 $O(\gamma)$。
第二类事件能够跳过中间部分，是因为出口对偶图为树。如果被跳过的源点能看见另一个目标区域，那么两条视线、源边界和目标边界围出的闭曲线，必被通向该区域的某条出口切开。这条出口的端点于是产生一个必须先处理的命中，与事件选择矛盾。源位置始终向前，第一类事件消耗一个旧源端点，第二类事件报告一个旧目标出口端点，各端点只会报告常数次。交换 $C_1,C_2$ 再扫描一次，总事件数为 $O(k_1+k_2)$。
旧出口仍有效就保留，被另一条子折线截断就替换；连接点补入常数个新端口。合并后区域的度数仍有常数上界，按端口入射顺序计数可取 $18$。接下来把度数恢复到 $4$。
分割引理。 度数超过 $4$ 的区域内，存在连接两条不相邻原始边界弧的水平可见出口；加入它以后，两侧区域的度数都严格下降。
为说明存在性，设想把该区域的全部顶点视线补齐。所得小区域度数至多为 $4$，其出口对偶图是一棵树。将旧出口视为树上的标记叶子；至少有五个标记时，必有一条树边把至少两个标记与至少另外两个标记分开，否则所有标记只能接在一个度数至少为五的中心上。对应的新出口正好连接两条不相邻的旧弧。
找到这条出口时，不必展开两条长弧。枚举常数对不相邻弧，将源弧拆成二进制规范块。在某个长度为 $t$ 的块内，使用已经建好的子图，把出口对偶树递归二分：找树重心，再切断最大的相邻分支。树的最大度数为常数，所以两部分都占固定比例，搜索深度为 $O(\log(t+2))$。
每次二分只需判断目标弧能够看见哪一侧。设分隔出口为 $uv$。从位于当前源弧上的端点向当前区域内部射线：命中目标弧就结束；否则这些视线与 $uv$ 构成至多两段水平屏障。如果 $uv$ 没有被当前区域的其他边界截断，直接用 $uv$；若被截断，就用从两端到首次边界的两段。只有一个端点位于源弧时，只需该端点的一段；两个端点都不在源弧时，源弧本来就完全位于分隔的一侧。
目标弧未被命中，因而完全处于切割后的某一部分。该部分只接触源弧的至多一类位置。另一类若能看见目标弧，视线就必须穿过某段水平屏障；不同高度的水平线不能相交，同一高度则由首次命中的端口顺序决定。因此整类都可以排除，搜索只进入一个孩子。
这个判断可以直接按边界次序执行：列出源块两端、$u,v$、至多两个命中点以及目标弧所在位置，沿目标所在部分的边界走一圈；遇到屏障端点就跳到配对端点。总共只有常数个位置。到叶子后，才检查该叶子所含的原始顶点。
为使分隔出口避开规范块的连接端点，先删除接触块两端的至多四条出口。每个新区域至多合并五个旧区域，所以叶子仍只含 $O(t^{1/5})$ 个原始边界元素。一次树下降使用 $O(\log(t+2))$ 次局部射线，叶子再用 $O(t^{1/5})$ 次。对长度至多为 $\gamma$ 的整条弧求和，共 $O(\gamma^{1/5}+\log^2(\gamma+2))=O(\gamma^{1/5})$ 次射线。
当前区域度数为常数，每条弧长度至多为 $\gamma$，所以一次局部射线耗时 $f(\gamma)=O(\gamma^{11/15})$。恢复一个区域的保形性总共只需常数次分割，费用为 $O(\gamma^{1/5}f(\gamma))=O(\gamma^{14/15})$。恢复以后，再按上一节的规则删除出口，得到所需粒度。
先建子链层次，再逐层细化
对原折线建立二进制分块层次。长度 $m=2^j$ 的规范块使用粒度 $\gamma_j=2^{\lfloor j/5\rfloor}$；由两个孩子合并，恢复保形性，删除多余出口，然后建立射线查询和树搜索结构。常数大小的块直接构造。
一个规范块只有 $k=O(m^{4/5})$ 个稀疏元素。合并做 $O(k)$ 次局部查询，保形性恢复耗时 $O(k\gamma_j^{14/15})$；平面图分块可用确定性排序完成，预处理耗时 $O(k\log^2(k+1))$。于是单个规范块的总费用为 $O(m^{74/75})$。所有局部射线只涉及长度 $O(\gamma_j)$ 的弧，所需规范块都在更低层，已经建好。原始顶点存放在共享数组中，无须为当前块重新扫描或复制。
第 $j$ 层至多有 $n/2^j$ 个规范块，故整个向上阶段满足
$$ T_{\mathrm{up}}(n)=O\!\left(n\sum_{j\ge0}2^{-j/75}\right)=O(n),\qquad S_{\mathrm{up}}(n)=O\!\left(n\sum_{j\ge0}2^{-j/5}\right)=O(n). $$
任意长度为 $m$ 的连续子链，先取它的二进制覆盖，再平衡合并这些规范块。保留一个对数因子就足够：其子图可以在 $O(m^{74/75}\log(m+2))$ 时间内构造。
至此，整条折线已有粒度约为 $n^{1/5}$ 的稀疏子图。还需把所有长弧细化，直到完整水平分解出现。设当前粒度为 $\Gamma=2^j$。每个区域至多有四条原始弧，每条弧含至多 $\Gamma$ 条边；用它们及常数条旧出口组成一个辅助边界。
辅助边界要保留双侧边界的顺序。沿用前述扫描高度，将重合边界的两份副本稍作分离，再略微倾斜旧水平出口。三种扰动的顺序取 $0<\delta\ll\eta\ll\varepsilon$：$\varepsilon$ 决定原始高度顺序，$\eta$ 分离副本，$\delta$ 倾斜出口。在一条原始边副本的内部删去一个无穷小开区间，避开所有原始事件顶点，再将两端作为折线端点。长弧仍只保存原边界区间，显式新增的连接段数为常数。
令辅助粒度 $\gamma=2^{\lfloor j/5\rfloor}$。辅助折线由常数段原始子链副本和常数段至多三条边的连接折线组成。对子链取已有的规范覆盖并复制端口次序，对连接折线直接构造，再按上一节的方法合并、恢复保形性。射线落在原始部分时查询已有索引，落在连接部分时直接检查常数条边。这样便构造出辅助折线的保形子图。随后先令 $\delta\to0$，再令 $\eta\to0$，把新出口投影回原区域，并保留所有旧出口。这一步始终保留 $\varepsilon$，区域内部也按保留该剪切的平面理解。重新闭合开口只会分割区域，不会合并区域。
投影时，一条出口的极限最多经过一个原始事件顶点；在该顶点处分开，故每条辅助出口至多产生两条有效出口。若出口撞到倾斜的旧出口，应保留极限中仍位于原区域内的部分；重合且端口相同的出口合并。这样，辅助分解在原区域内部留下的每一段极限分隔都被保留。
这一覆盖性质给出细化后的大小界。取投影结果某个开区域内部的任意紧路径，它避开所有极限分隔，因此在充分小的扰动下也避开所有辅助出口。路径上的点必落在同一个辅助区域内。于是一个输出区域的原始边界只可能来自同一个辅助区域的至多四条弧。
四条辅助弧各含至多 $\gamma$ 条原始边，端点还原至多增加八个残片，所以每条输出弧的权重至多为 $4\gamma+8$。一个辅助区域的四条出口各分成至多两条，再加原区域的至多四条旧出口，输出区域度数至多为 $12$。恢复保形性并删除多余出口后，可取下一粒度 $\Gamma'=2^{\lceil\log_2(4\gamma+8)\rceil}$。只要 $\Gamma>16$，就有 $\Gamma'<\Gamma$。
现在算向下阶段。粒度为 $\Gamma$ 时有 $O(n/\Gamma+1)$ 个区域；一个区域的辅助构造耗时 $O(\Gamma^{74/75}\log(\Gamma+2))$，因此一轮总费用为 $O(n\log(\Gamma+2)/\Gamma^{1/75})$。局部投影的排序和保形性恢复也落在这个界内。所有粒度都是严格下降的二次幂，每个指数最多出现一次，于是
$$ T_{\mathrm{down}}(n) =O\!\left(n\sum_{j\ge5}(j+1)2^{-j/75}\right) =O(n). $$
当 $\Gamma\le16$ 时，每个区域至多含四条、每条至多十六条边的原始弧。直接在这个常数规模区域内补齐全部顶点水平视线即可。所有区域合计为 $O(n)$，因此得到完整水平分解的总费用仍为 $O(n)$。
最后补回最初删去的多边形边。它不会穿过其他原始边，只需沿水平分解经过的区域前进，在每个常数大小的单元中切开，保留多边形内部的一侧，再将单元三角化。新增边界点和三角形总数均为 $O(n)$。沿原边界合并已有有序位置给顶点编号，再按两个端点编号做两趟计数分配，即可在线性时间内建立三角形邻接。
共线时保留边界端口及零面积极限三角形的邻接关系；这些对象不改变上述计数。真正零长的端口区域由边界次序直接处理。零面积三角形按其三顶点的有限凸包裁剪，只传递入口区间，不贡献二维可见片。具有非零角宽的区间仍可穿过这样的三角形，最后只取二维可见片的闭包。扰动只用于确定分解的组合结构，最短路始终在原多边形中计算。
每个规范块、旧分解和当前辅助构造只保存线性总量的稀疏记录；向下阶段处理完一层即释放旧层。因此整个三角剖分使用 $O(n)$ 时间和 $O(n)$ 空间。
用两条最短路求到整个窗口的距离
先求 $g$ 到窗口两个端点 $a,b$ 的最短路。定位端点所在三角形，在对偶树中取连接源、目标三角形的唯一通道。任何离开通道的支路都必须从同一条对角线返回，把这段路替换成对角线上的直线段不会更长，因此只需在通道内部求最短路。
通道中相邻三角形的公共边称为门，按从源三角形到目标三角形的行进方向规定它的左、右端点。依次经过这些门，维护已经确定的最短路前缀、前缀末端 $z$，以及从 $z$ 到当前门两端的两条凸链。左链只保留严格左转，右链只保留严格右转；它们围成尚未确定的漏斗。
加入新的左端点时，从左链尾部删除不满足左转的点。如果新方向越过右链的第一条支撑边，最短路就必须经过右链的下一个顶点，于是把该段加入公共前缀，并把漏斗顶点推进到那里。重复直到新方向回到漏斗内部。右端点的更新完全对称。最后把目标点同时作为门的两个端点，漏斗就收束成目标最短路。
这些操作可以用拉紧路径来证明。被删除的链顶点对应一段能够在通道内拉直的折线；新方向跨过另一侧支撑边时，那一侧的第一个转折已无法绕过，因而成为所有后续路径的公共前缀。每个门只处理一次，每个链顶点只入队、出队常数次，所以一条端点最短路耗时 $O(n)$。这就是三角剖分中的线性最短路所用的漏斗维护。
记求出的两条路径为 $\pi_a,\pi_b$。若 $\pi_a$ 首次在 $a'$ 碰到窗口，它的后缀必为直线段 $[a',a]$，否则沿窗口拉直即可缩短。最短路的每个前缀也最短，所以任意 $x\in[a,a']$ 都满足 $d_P(g,x)=d_P(g,a')+|a'-x|$。因此可删去这段目标区间，并在 $a'$ 截断路径。另一端同理得到 $b'$。两个首次接触点不能次序颠倒，否则同时有 $d_P(g,a')=d_P(g,b')+|a'b'|$ 及其反向等式，除非 $a'=b'$。重合时直接得到答案；其余情形把剩余目标区间重新记为 $[a,b]$。
去掉两条路径的几何公共前缀，设其末端为 $z$、长度为 $D_0$。公共前缀按线段重合比较；同一直线上的多余中间顶点不影响它。两条最短路分开以后不会重新汇合：否则它们围成一条 Jordan 曲线。由于 $P$ 无洞，曲线围住的区域也在 $P$ 内。两处交接点的转角不足以贡献全部 $2\pi$，所以还存在一个可以向区域内部拉直的凸角，与最短性矛盾。
剩下的两条凸链与 $[a,b]$ 围成一个漏斗。路径若越出两条端点最短路围成的区域，就把它从离开到返回的部分替换成相应端点最短路的子路径，长度不会增加。因此总能在该区域内取得最短路。把路径拉紧后，它只可能在两侧凸链上转折；链的凸性使支撑线按次序扫过窗口。于是到窗口任一点的最短路都由公共前缀、某一侧凸链的前缀和最后一条直线段组成。若最后一次转折在顶点 $u$，其长度就是 $D(u)+|u-x|$，其中 $D(u)$ 是从 $g$ 沿对应路径到 $u$ 的长度，可以顺着两条链累计得到。
下面直接求每个 $u$ 负责的窗口区间。定义 $\Delta(p,q,r)=(q-p)\times(r-p)$，将窗口参数化为 $x(t)=a+t(b-a)$，$0\le t\le1$。必要时交换 $a,b$，使从 $z$ 到 $a$ 的路径为左链，从 $z$ 到 $b$ 的路径为右链。分别记为 $z=l_0,l_1,\ldots,l_p=a$ 和 $z=r_0,r_1,\ldots,r_q=b$。
对于漏斗顶点 $z$，不再转折就能到达的部分满足 $\Delta(z,l_1,x(t))\le0$ 和 $\Delta(z,r_1,x(t))\ge0$，不存在的链边不加限制。对于左链顶点 $l_i$，它成为最后一次转折的位置需要满足 $\Delta(l_{i-1},l_i,x(t))\ge0$；若存在后继，还需 $\Delta(l_i,l_{i+1},x(t))\le0$。右链使用相反的不等号。
第一条限制要求路径确实在当前点转折，第二条限制要求尚未进入必须绕过下一顶点的范围。链的凸性保证这两个相邻支撑条件已经足够。每个条件都是关于 $t$ 的一次不等式，与 $[0,1]$ 相交后得到一个区间 $I_u=[\alpha_u,\beta_u]$，也可能为空。所有非空区间覆盖整条窗口；公共端点处的多个表示给出相同的拉紧路径。
在 $I_u$ 内，$D(u)$ 固定，只需最小化点到线段的欧氏距离。令 $v=b-a$，将垂足参数 $(u-a)\cdot v/|v|^2$ 截到 $I_u$ 内，即得到该区间的最优位置。因此
$$ t_u=\min\!\left(\beta_u,\max\!\left(\alpha_u,\frac{(u-a)\cdot v}{v\cdot v}\right)\right),\qquad \operatorname{ans}=\min_{u:I_u\ne\varnothing}\bigl(D(u)+|a+t_uv-u|\bigr). $$
若目标线段已缩成一个点，直接返回该点的最短路长度。否则每个链顶点只做两次线性不等式裁剪和一次投影，整个窗口最短路阶段为 $O(n)$。
三角剖分、可见区域、窗口选择和漏斗处理合计为确定性的 $O(n)$ 时间、$O(n)$ 空间。最坏情况下，任意一个未检查的凹口都可能改变可见性或最短路，故还需要 $\Omega(n)$ 时间；最终时间复杂度为 $\Theta(n)$。
参考文献
- 本题官方题解视频。
- Bernard Chazelle. Triangulating a Simple Polygon in Linear Time. Discrete & Computational Geometry, 6:485–524, 1991.
- Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert E. Tarjan. Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons. Algorithmica, 2:209–233, 1987.
- Richard J. Lipton, Robert E. Tarjan. A Separator Theorem for Planar Graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
- CGAL. 2D Visibility: Regularized Visibility.