平面最近点对——分治
初见思路
什么嘛一看就只会暴力
后面想用分治，可是不知道怎么样拿掉一个问题，令剩下的问题变成子问题
正解
被点分治的概念限制住了
发现分治大概可以分成几种
- 一种是互相独立，拿掉一块之后分裂成两个问题
- 比如点分治
- 另一种是利用处理子问题的结果优化更大问题
- 可以类比搜索，可以拿子问题的答案做"剪枝"
- 比如这题，还有归并排序
- 考虑两大块之间互相贡献？
- 像CDQ(还没学)，之前见到的floyd
这题是第二种
考虑已经有了左右两半的答案
此时考虑两边的点哪些可能更优
假设两侧得到的答案为d
首先肯定要找相互横坐标之差小于d的，否则不如直接用d
其次纵坐标之差也必须也得小于d，同理
此时会发现如果在两边的话，必须到中间的距离都小于d
再接着会发现，此时范围已经被框定为了一个矩形，此时将矩形内的点逐个配对即可
关于左右边界的划定对复杂度的影响
因为可以证明以一个点展开的矩形内的点不超过5个，所以此时复杂度是常数级的
但是如果没有左右边界呢
也就是说所有点按y排序，每个点常数级，复杂度还是n log^2 n嘛
试验了一下不是，这个只在划分了左右边界时成立
比如一个显然的反例:
关于分治的思考
分治分治，分而治之，但是这个思想有点太过笼统
应当是发现子问题的结构，去除掉一个规模大而"空"的问题，拆分成规模更小的子问题
然后利用解决子问题后/解决大问题后 的性质快速解决剩下的问题
以及利用分治的划分充分利用重叠的子问题