P13182 [GCJ 2017 Finals] Omnicircumnavigation

Rigel · 2026-04-23 15:37:44 · 题解

期望复杂度 \mathcal{O}(T N \log N) 的做法。

问题可以转化为是否存在一个开半球严格包含所有点。若是，则答案为 \texttt{NO}，否则为 \texttt{YES}。

先对点集去重。

首先特判两种 case。

• 若存在对跖点对，则为 \texttt{YES}。

• 若去重后剩余点数 \le 2 且不存在对跖点对，则为 \texttt{NO}。

然后求出所有点与原点的三维凸包。

找到凸包上所有包含原点的面。

• 若不存在包含原点的面，则原点严格在凸包内部，即其他点不在同一半球，答案为 \texttt{YES}。

• 若这些面均平行，说明原点在凸包表面上，即恰好存在一个闭半球包含其他点，答案为 \texttt{YES}。

• 若这些面不平行，说明原点是凸包的顶点，即存在一个开半球包含其他点，答案为 \texttt{NO}。

还有一种 case：在选取三维凸包初始点时，若找不到四个不共面的点，则说明所有点都在过原点的平面上。设该平面法向量为 \boldsymbol{n}。考虑在点集中新增一个点 (0,0,0)+\boldsymbol{n}，然后求所有点的三维凸包，判原点是凸包的顶点还是在凸包表面即可。该方法显然正确。

时间复杂度瓶颈在求三维凸包，期望为 \mathcal{O}(N \log N)。故总复杂度为 \mathcal{O}(T N \log N)。

Submission，用时在 300 ms 左右，目前是洛谷与 QOJ 上的最优解。

upd：将向量运算过程中可能会爆 long long 的地方改成了 __int128，用时在 400 ms 左右，仍然是最优解。Submission。