本题是否存在复杂度正确的非乱搞做法？

如大家所见，在将本质相同的乱搞题解和被卡飞的分治题解（以及另外一篇套用 https://www.luogu.com.cn/article/5biq6msl 思想的同样被卡飞的题解）撤下后，现在只剩下两篇题解，其中一篇是可以被卡到 $\Omicron(n^2)$ 的 K-D Tree，剩下一篇是没有正确性保证的乱搞。

因为本题的点分成了两类，平面最近点对几乎所有的优化思想都失效了（可以看我在工单里给出的 Hack）。本题是否存在复杂度正确且保证正确性的做法？