记一次讨论

发表于 2025-03-22

某物理老师在公开课上使用 AI 生成的 HTML 动画演示分子热运动。我对其碰撞检测的算法产生了兴趣。研究代码后发现，除去各种 bug，它甚至在使用单次 $O(n^2)$ 的暴力算法检测碰撞……

……就这点破事值得写一篇文章吗 QAQ……

……我现在连这种简单问题也解决不了吗 QwQ……

问题描述

有 $n$ 个大小相等的小球进行无序运动，对于某一时刻，我们想知道所有发生碰撞的小球。

形式化地说，在平面上有 $n$ 个点对近似均匀分布，求所有距离小于等于 $2r$ 的点对，$2r \ll \text{点之间的平均距离}$（可以认为所求点对数目最大为 $O(n)$）。

我们需要优于 $O(n^2)$ 的算法。

与 NAPeach 讨论，并很快偏离话题

发现 neko_yizhexu，遂与 neko_yizhexu 讨论

neko_yizhexu: （使用你谷平面最近点对的乱搞算法）将每个点旋转某角度，对 $x + y$ 排序，取每个点周围 $50$ 个点进行比较 ——$O(n \log n)$，瓶颈在于排序
unsigned_char: 对点的 $x$ 座标排序后遍历，使用平衡树或线段树维护 $y$ 座标，对于 $y$ 座标相近的点使用栈维护，每遍历到一个点后查询与其 $y$ 座标相近的点，取栈顶 ——近似 $O(n \log n)$
neko_yizhexu: （就 unsigned_char 的方法）不使用 DS，以 $\sqrt{n}$ 为块长分块 —— $O(n \sqrt{n})$

neko_yizhexu 发现听取MLE声一片和岂非，并邀请二人加入讨论

听取MLE声一片: （可以认为是点重合吗？……）以 $4r \times 4r$ 为一个像素，将点映射到像素上，用 map 维护 ——$O(n \log n)$ 取决于map 的实现方式

完结撒花