具体分析见编程之美解法三，借鉴网上的代码，但其有错误，再次修正。 代码如下：
#include <stdio.h> #include <algorithm> #include <vector> #include <math.h> #include <stdio.h> #include <algorithm> #include <vector> #include <math.h> using namespace std; class Point { public: Point(int x,int y):x_(x),y_(y){} Point():x_(0),y_(0){} static bool OrderByY(const Point &left,const Point &right) { return left.y_ < right.y_; } static bool OrderByX(const Point &left,const Point &right) { return left.x_ < right.x_; } public: int x_; int y_; }; double Distance(const Point& left, const Point& right) { return (sqrt(pow((double)(left.x_-right.x_),2) + pow((double)(left.y_-right.y_),2))); } //采用分治归并思想求多点之间的最小距离=min(left最小距离，right最小距离，left和right分别对应的最靠近的点的距离) //left和right分别对应的最靠近的点的距离只可能出现在min_distance * （2*min_distance）的区域内，min_distance为纵坐标长度， //2*min_distance横坐标长度，以min_distance为原点。 double NearestPoints(const vector<Point>& points, int start, int end, Point *point1, Point *point2) { if(end > start) { int middle = (start + end) / 2; Point point1_l,point2_l,point1_r,point2_r; double left_distance = NearestPoints(points,start,middle,&point1_l,&point2_l);//保留左边最小值的坐标对 double right_distance = NearestPoints(points,middle+1,end,&point1_r,&point2_r);//保留右边最小值的坐标对 double min_distance = left_distance > right_distance ? right_distance : left_distance; if(left_distance > right_distance) { *point1 = point1_r; *point2 = point2_r; } //暂时保留的是除了中间带状区域的最小距离的坐标对 else { *point1 = point1_l; *point2 = point2_l; } vector<Point> left_part_points; for(int i = start;i <= middle;++i) { if(points[middle].x_-points[i].x_ <= min_distance) left_part_points.push_back(points[i]); } sort(left_part_points.begin(),left_part_points.end(),Point::OrderByY); vector<Point> right_part_points; for(int i = middle+1;i <= end;++i) { if(points[i].x_ - points[middle].x_ <= min_distance) right_part_points.push_back(points[i]); } sort(right_part_points.begin(),right_part_points.end(),Point::OrderByY); int distance_y = 0; double d = 0; for(int i = 0;i < left_part_points.size();++i) { for(int j = 0;j < right_part_points.size();++j) { distance_y= left_part_points[i].y_ > right_part_points[j].y_ ? left_part_points[i].y_ - right_part_points[j].y_ : right_part_points[j].y_ - left_part_points[i].y_;//使两个点的相对坐标要在min_distance之内 if(distance_y <= min_distance) { d = Distance(left_part_points[i],right_part_points[j]); if(d < min_distance) { min_distance = d; *point1 = left_part_points[i]; *point2 = right_part_points[j]; } } } } return min_distance; } else return 0x7FFFFFFF; } int main() { std::vector<Point> points; points.push_back(Point(2,3)); points.push_back(Point(1,4)); points.push_back(Point(3,0)); points.push_back(Point(1,5)); points.push_back(Point(0,5)); sort(points.begin(), points.end(), Point::OrderByX); Point point1; Point point2; NearestPoints(points, 0, points.size() - 1, &point1, &point2); printf("Point1: (%d, %d) <--> Point2: (%d, %d)\n", point1.x_, point1.y_, point2.x_, point2.y_); system("pause"); }