type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于我的个人博客：欢迎大佬们来逛逛
给你一些点，求两点之间距离最小的两个点之间的最短距离。
分治算法是解决这类问题的关键。
Solution
首先将所有的点按照 为第一关键字， 为第二关键字进行排序。
排序后如下：
我们可以将所有的点分治：
在这些点中我们用一条分割线来隔开，如果我们一直分割，则到最后 的时候，就表明划分到了最后的两个点，因此直接计算两个点之间的距离；如果最后只有一个点，即 ，则我们规定此距离为无穷大。
因此我们得到两个点之间距离之后再回溯，寻找相对于这两个点有没有更优的点对出现，则更新，继续回溯。最后结束的时候，我们一定可以得到所有点的距离最短的距离。
树型图表示如下：
- 首先递归到 发现此时只有 两个点，因此我们计算他们的最短距离，假设为 3
- 接着进入 此时只有一个点，因此规定距离为无穷大
- 然后我们回溯到 ，取两个孩子节点的最小值，为3；但是此时并没有结束，我们获得的 3 只是分割线两侧分别计算的最优解，我们此时还需要得到去除分割线之后的所有点的之间的最短距离，更新为 之间的距离，为 2.
- 然后递归到 区间，得到 之间距离为 2.5。
- 然后回溯到 根节点 ，得到分割线两侧的点之间的最优解，为2；接着计算去除分割线之后的两点之间的最优解，得到 1.2 ，为 之间的距离
如何计算去除分割线之后的区间的两点的最短距离？
我们称之为 跨中线处理
- 首先由目标区间 得到所有 的差值小于 的点集合。
- 将这些点按照 值排序
- 最后直接两两之间暴力枚举 值的差值小于 的点对距离
流程
因此我们很轻松的得到分治求平面最近点对的流程：
- 首先将所有的点按照 和 为第一第二关键字排序。
- 然后递归分治所有的点，递归到终点时计算点的距离，回溯返回局部最优解。
- 然后计算全局最优解，即跨中线处理。
时间复杂度：
使用归并排序会降低为
完整模板代码
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/0865b402-a713-46ae-9f14-9f7cb07d8c81
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。