空间最近点对问题是否有随机旋转的处理
查看原帖
空间最近点对问题是否有随机旋转的处理
73994
光与影皆寂寞楼主2023/11/20 16:31

RT,起因是看到了这个(P7883第一篇题解)


我们充分发扬人类智慧:

将所有点全部绕原点旋转同一个角度,然后按 x×y 排序

根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远

所以我们只取每个点向前的 50 个点来计算答案

这样速度快得飞起,在n=400000 时都可以在 124ms 内卡过


想问一下在三维空间中是否存在类似的操作呢?

2023/11/20 16:31
加载中...