题解 P7883 【平面最近点对（加强加强版）】

zhoukangyang · 2021-10-13 09:37:28 · 题解

我们充分发扬人类智慧：

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

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

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

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