题目链接：https://www.codewars.com/kata/5376b901424ed4f8c20002b7/train/python

对应算法导论的 33.4。

主要是有几个问题。

1、分治是如何进行切分的？

我是比较朴素地直接一分为二，不让在中间的分割线上既可以包含在左半部分也包含在右半部分。而且，中间的线上的点是先从上面的部分切起，保证这一点的做法是，把点集按照 x 坐标排序的同时，如果 x 相等，那么，再按 y 排序。

2、真的是 O(nlogn) 吗？

是的。不信你就去用主方法再推一遍。

3、为什么可以是 5 而不是 7？

因为我前面的切分保证了分割线上没有重复的点。

4、如何保证每一次递归额外所花费的时间是 O(n)？

对 Y 切割后进行排序使用 set，那么，基本可以保证每一次查询是 O(1) 的时间复杂度。而构建 set 的插入操作也是这个时间复杂度。不过，正如我们学习数据结构的时候知道，有些极端情况会退化成 O(n) 的，但是，这个极端情况也是可以通过进一步优化 set 的内部构造来解决的。所以，这里按下不表，单就做题而言，使用 Python 内置的 set 就可以了。

5、为什么只用 X 和 Y 就可以了？

因为 P 其实本来就用不到，书上是为了事无巨细地讲明白才如此冗余。

6、对于中间条带的点的暴力循环，其时间复杂度是 O(n)？

当然是的，5n 也是 O(n)，不是吗？

其实，我以前在上课的时候，也写过一篇[笔记](https://fanlumaster.github.io/2021/05/03/《算法导论》寻找最近点对问题的 Python 实现)。

代码见仓库。