杂题乱做3

agc077e. Hamiltonian Path Inversion

太牛了，做法请参考 https://www.luogu.com.cn/article/qya2scgp

SDCPC2026 M. Night at the Museum 2

不是很懂这个题为什么场上过的队这么少。

令 $n$ 为巡逻折线的点数，$m$ 为展品数量。我们需要寻找闭合路线中使得所有展品都在视野内的路径总长度。

由于视距无限，展品可见的唯一限制是视角。考虑单条线段，起点为 $A$，终点为 $B$。定义线段方向向量为 $\vec{v} = B - A$。线段上的位置可参数化为 $P(t) = A + t\vec{v}$，其中 $t \in (0, 1)$。

对于 $m$ 个展品中的任意节点 $Q$，令 $\vec{u} = Q - A$。从 $P(t)$ 看向 $Q$ 的视线向量为 $\overrightarrow{P(t)Q} = \vec{u} - t\vec{v}$。

注意到 $\vec{v} \times (\vec{u} - t\vec{v}) = \vec{v} \times \vec{u}$，该值与参数 $t$ 绝对无关。

定义常数 $C = \vec{v} \times \vec{u}$ 以及 $D = \vec{v} \cdot \vec{u}$。满足展品在视野内的充要条件是视线向量与 $\vec{v}$ 的夹角不超过 $a$。条件可以表示为：

$$|C| \le (D - t|\vec{v}|^2) \tan a$$

考虑通过去绝对值将其转化为对参数 $t$ 的最值约束：

$$t \le \frac{D \pm C \cot a}{|\vec{v}|^2}$$

令查询向量 $\vec{w}_{1} = (v_x - v_y \cot a, v_y + v_x \cot a)$，$\vec{w}_{2} = (v_x + v_y \cot a, v_y - v_x \cot a)$。

现在考虑一个全新的问题：将上述限制式的分子展开，其实质上是求 $Q$ 落在 $\vec{w}$ 方向上的投影，即 $Q_x w_x + Q_y w_y$（差一个仅与 $A$ 相关的常数）。使得 $t$ 存在合法解的充要条件是找到所有 $Q$ 在对应方向投影的最小值，以获取最严苛的 $t$ 上界。

很经典的作法是将所有展品的位置状态构建为一个严格二维凸包。

我们在凸包外部额外维护一个极角序列，表示凸包每条边的外法线极角。

当我们枚举 $n$ 条线段并在极角序列上二分查找 $\vec{w}$ 时，能直接在 $O(\log m)$ 内定位到最小投影点。算出双边界最严苛的上限 $T_{max}$，将其与 $[0, 1]$ 取交集，得到的区间长度乘上 $|\vec{v}|$ 即为合法路径长。时间复杂度 $O((n+m)\log m)$。