C++_最接近点对问题 C++_最接近点对问题

1. 问题描述

问题描述：最接近点对问题，即在平面上给定n个点的情况下，寻找其中的一对点，使得这对点之间的距离在所有可能的点对中为最小。

1. 设计思路

设计思路：假设集合S中的各个点均为平面上的坐标点，每个点都具有x和y两个坐标值。为了将整个平面内的点集S线性划分为两个规模大致相等的子集S1与S2，我们选择一条垂直于x轴的直线l:x=m作为分割线。其中m为集合S中所有点x坐标的中位数值。通过该分割方式，可以将S划分为两部分：S1={p∈S|px≤m}与S2={p∈S|px>m}。这样，集合S1中的所有点均位于直线l的左侧，而集合S2中的所有点则位于直线l的右侧，并且满足关系式S=S1∪S2。由于m是集合中各元素x坐标的中位数，因此子集S1与子集S2所包含的元素数量基本一致。接下来，在子集S1和子集S2上分别递归地求解最接近点对问题，并得到各自的最小距离d1和d2。设d=min(d1,d2)。如果整个集合中最接近的一对点(p,q)之间的距离d(p,q)小于d，则说明该对点必定分别属于子集S1和子集S2。不妨假设p∈S1且q∈S2，则此时p与q到分割线l的距离均小于d。因此，若用P1表示位于分割线l左侧、宽度为d的垂直长条区域，并用P2表示位于分割线l右侧、宽度同样为d的垂直长条区域，则可以得出p∈P1且q∈P2的结果，如图所示：

![](https://cdl.itad