6 个解决方案
#1
Voronoi图
#2
老兄能否给全部代码，或链接呀？
#3
分治法
#4
up again
#5
王晓东的《算法设计与分析》 电子工业出版社
《最近点对问题》有详细介绍
《最近点对问题》有详细介绍
#6
分治法可以解。
Divide：
首先考虑各个点的x坐标，找出他们的中位数xd（可以看一看找中位数的算法，他可在线性时间内完成，前几天，有人问过这个算法，我有详细的解答），用xd将这些点分成两部分，对各个部分递归调用此算法。
Merge：
在merge阶段除了要比较在这两个部分得到的解（设两部分中较小的点对距离为d），还要比较x＝xd这条线左右d范围内点的距离大小，其实，只用对x＝xd左侧在|x-xd|<=d范围内的每一个点计算其到右侧相应范围内点的距离即可。我们可以证明，对左侧该范围内的一点，最多计算在其相近距离内6个点就能得到答案（用鸽巢原理）。这样，在比较它与d的大小，可得到答案。
Divide：
首先考虑各个点的x坐标，找出他们的中位数xd（可以看一看找中位数的算法，他可在线性时间内完成，前几天，有人问过这个算法，我有详细的解答），用xd将这些点分成两部分，对各个部分递归调用此算法。
Merge：
在merge阶段除了要比较在这两个部分得到的解（设两部分中较小的点对距离为d），还要比较x＝xd这条线左右d范围内点的距离大小，其实，只用对x＝xd左侧在|x-xd|<=d范围内的每一个点计算其到右侧相应范围内点的距离即可。我们可以证明，对左侧该范围内的一点，最多计算在其相近距离内6个点就能得到答案（用鸽巢原理）。这样，在比较它与d的大小，可得到答案。
#1
Voronoi图
#2
老兄能否给全部代码，或链接呀？
#3
分治法
#4
up again
#5
王晓东的《算法设计与分析》 电子工业出版社
《最近点对问题》有详细介绍
《最近点对问题》有详细介绍
#6
分治法可以解。
Divide：
首先考虑各个点的x坐标，找出他们的中位数xd（可以看一看找中位数的算法，他可在线性时间内完成，前几天，有人问过这个算法，我有详细的解答），用xd将这些点分成两部分，对各个部分递归调用此算法。
Merge：
在merge阶段除了要比较在这两个部分得到的解（设两部分中较小的点对距离为d），还要比较x＝xd这条线左右d范围内点的距离大小，其实，只用对x＝xd左侧在|x-xd|<=d范围内的每一个点计算其到右侧相应范围内点的距离即可。我们可以证明，对左侧该范围内的一点，最多计算在其相近距离内6个点就能得到答案（用鸽巢原理）。这样，在比较它与d的大小，可得到答案。
Divide：
首先考虑各个点的x坐标，找出他们的中位数xd（可以看一看找中位数的算法，他可在线性时间内完成，前几天，有人问过这个算法，我有详细的解答），用xd将这些点分成两部分，对各个部分递归调用此算法。
Merge：
在merge阶段除了要比较在这两个部分得到的解（设两部分中较小的点对距离为d），还要比较x＝xd这条线左右d范围内点的距离大小，其实，只用对x＝xd左侧在|x-xd|<=d范围内的每一个点计算其到右侧相应范围内点的距离即可。我们可以证明，对左侧该范围内的一点，最多计算在其相近距离内6个点就能得到答案（用鸽巢原理）。这样，在比较它与d的大小，可得到答案。