最近点对问题 ---分治算法
n个点在公共空间中，求出所有点对的欧几里得距离最小的点对。
1.暴力**,时间复杂度(n^2),太大了,不方便
2.分治算法, 最近点对问题和在一个数组中求最大序列和问题的思路是相似的
用结构体数组保存在笛卡尔坐标系上的点,按照x升序排列,找到x坐标数组中 中间的那个 作为分界线 ,平衡子
最小点对有三种情况,要么分别在分界线两边,要么经过分界线(可以一段在分界线上)
求左右边的最近点对可以进行递归操作,再次进行分治操作,当最后点只剩2-3个时,就进行直接运算,三个点之间距离进行比较,两个点就直接返回距离
当左右两边的最近点对求出以后,再比较得到两边最近点对中更小的那个,标记为d,再来考虑第三种情况
第三种经过分界线的情况也存在两种,一种存在最近点对,一种不存在.如果存在,则两点之间的x差值和y差值一定小于左右两边的最小点对(容易证明得到),所以第三种情况的两点x坐标一定在x的分界线左右两边d的范围内,且他们y坐标的差值一定在d以内.
如果我们将x坐标在x的分界线左右两边d的范围内的点 的y坐标两两进行比较的话,复杂度也在n^2范围内,就无法得出比暴力**法更好,但我们知道y坐标的差值也在d以内,所以我们将结构体数组按照y升序排列,并且求出x在范围内的点 这个的时间复杂度为n 遍历这些求出的点,每个点都要跟他们后面y差值为d的点的距离和d进行比较,如果小于d 就等于这个距离,如果大于,第一个点不动,第二个点遍历到下一个点,如果y的差值大于d, 就将第一个点选择为y值增大最小的下一个点(按照y排序数组的下一个),知道第一个点遍历到数组的倒数第二位
在这个算法中还要注意的一点为距离除了返回值以外,最好不要用开方,也就是不要去求出距离,用他们的两边平方和的形式代替,开方的运算量很大
这样一层层的返回就能得到我们的答案了
时间复杂度nlogn