最近点对问题

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <ctime> 
#define MAX_DISTANCE 999999
using namespace std;

typedef struct point{
	double x;	//横坐标
	double y;	//纵坐标 
}Point;

Point *PointsX;
Point *PointsY;
Point minPoint1, minPoint2;			//二维点最优数组 
int n;								//二维点个数 

//按横坐标升序排序规则函数 
bool cmpX(Point point1,Point point2)
{
	return point1.x < point2.x;
}

//按纵坐标升序排序规则函数
bool cmpY(Point point1,Point point2)
{
	return point1.y < point2.y;
}

//计算两点间的距离 
double Distance(Point point1,Point point2)
{
	double distx = pow(point1.x-point2.x,2);
	double disty = pow(point1.y-point2.y,2);
	return sqrt(distx+disty);
}

//归并排序的合并整理操作
void Merge(int left, int right)
{
 
	int mid = (left + right) / 2;
	int i = left, j = mid + 1;
	int idx = left;
 
	while(i <= mid && j <= right) {
		if (PointsX[i].y < PointsX[j].y){
			PointsY[idx++] = PointsX[i++];	
		}else{
			PointsY[idx++] = PointsX[j++];	
		} 
	}
 
	while(i <= mid){
		PointsY[idx++] = PointsX[i++];	
	} 
	while(j <= right){
		PointsY[idx++] = PointsX[j++];	
	}
	for(i = left; i <= right; i++){
		PointsX[i] = PointsY[i];
	}
}

double MergeMethod(Point *px, int l, int r, Point &p1, Point &p2)
{
	if(r - l <= 0){//点数为1时输出无穷大
		return MAX_DISTANCE;
	}else if(r - l == 1){		//点数为2直接输出点距同时记录点对
		Merge(l,r);
		p1 = px[l];
		p2 = px[r];
		return Distance(p1,p2);
	}else{
		Point c, d, e, f;
		double mindis;
		int i, j;
		int mid = (r + l) / 2;		//前面已排好序，直接平均分
		double middlex = PointsX[mid].x;	//记录中线的x值，用于后面判断和存储中间区域的点
		double mindis1 = MergeMethod(px, l, mid, c, d);		//求左边部分的最短点距
		double mindis2 = MergeMethod(px, mid+1, r, e, f);	//求右边部分的最短点距
		if(mindis1 < mindis2){		//两边比较取最小值，并记录点对
			mindis = mindis1;
			p1 = c;
			p2 = d;
		}else{
			mindis = mindis2;
			p1 = e;
			p2 = f;
		}
		Point *temp = new Point[r - l + 1];		//将所有与中间点的横坐标距离小于mindis的点纳入数组
		int number = 0;
		Merge(l, r);			//对点进行合并操作，之后的数组已是按y值排好的数组
		for(i = l; i <= r; i++){
			if(fabs(px[i].x - middlex ) <= mindis){	//数组内的数据相当于在横坐标范围[middlex-mindis,middlex+mindis]之间
				temp[number++] = px[i];
			}
		}
		double tempdis;		//遍历中间数组，每个点最多遍历其他点6次，记录最短距离和点对
		for(i = 0; i < number; i++){
			for(j = i + 1; j < i+1+6 && j < number; j++){
				tempdis = Distance(temp[i],temp[j]);
				if(tempdis < mindis){
					mindis = tempdis;
					p1 = temp[i];
					p2 = temp[j];
				}
			}
		}
		delete[]temp;
		return mindis;
	}
}

//随机生成点
void CreatePoints(Point* Points, int pointNumber)
{
	srand(time(NULL));		//随机化随机数种子
	for(int i = 0; i<pointNumber; i++){
		Points[i].x = rand() / (double)RAND_MAX;
		Points[i].y = rand() / (double)RAND_MAX;
		//每1000个数据乘以一个特定的数，将数据尽量分散，减少重复
		Points[i].x *= ((i / 1000) + 1);
		Points[i].y *= ((i / 1000) + 1);
		//遍历已经生成的所有点，一旦发现重合则重新生成该点
		for (int j = 0; j < i; j++){
			if (Points[j].x == Points[i].x && Points[j].y == Points[i].y) {
				i--;
				break;
			}
		}
	}
}

int main()
{
	cout<<"请输入二维点个数："<<endl;
	cin>>n; 
	PointsX = new Point[n];
	CreatePoints(PointsX, n);			//创建散点	
	cout<<"随机生成的二维点坐标为："<<endl;
	for(int i = 0 ; i < n ; i++){
		cout<<"("<<PointsX[i].x<<","<<PointsX[i].y<<")"<<endl; 
	} 
	sort(PointsX, PointsX + n, cmpX);		//对点以X坐标进行排序
	PointsY = new Point[n];		//创建新数组在Merge合并操作时用
	double dis = MergeMethod(PointsX, 0, n - 1, minPoint1, minPoint2);	//调用分治法
	if(dis == MAX_DISTANCE){
		cout<<"不存在最近点对"<<endl; 
	}else{
		cout<<"最近点对为："<<endl;
		cout<<"("<<minPoint1.x<<","<<minPoint1.y<<")"<<endl; 
		cout<<"("<<minPoint2.x<<","<<minPoint2.y<<")"<<endl; 
		cout<<"最近距离为："<<dis<<endl;	
	}
	
	return 0;
}