#include<iostream>
#include<algorithm>
#include<cmath>
#include<fstream>
#include <stdlib.h>
using namespace std;
typedef struct{
float x; //點的x,y坐標
float y;
}POINT;
//輔助點的結構
typedef struct{
int index; //點在x陣列中的下標
float x; //點的x,y坐標
float y;
}A_POINT;
bool compareX(POINT a,POINT b)
{
return b.x>a.x;
}
bool compareY(A_POINT a,A_POINT b)//對輔助點進行遞增排序的比較
{
return b.y>a.y;
}
float dist(POINT a,POINT b)//計算兩點距離的平方
{
float dx,dy;
dx=a.x-b.x;
dy=a.y-b.y;
return (dx*dx+dy*dy);
}
void closest(POINT X[],A_POINT Y[],int low,int high,POINT &a,POINT &b,float &d)
{
int i,j,k,m;
POINT al,bl,ar,br;
float dl,dr,dx;
if((high-low)==1)
{
a=X[low];
b=X[high];
d=dist(X[low],X[high]);
}
else
{
if((high-low)==2)
{
dl=dist(X[low],X[low+1]);
dr=dist(X[low],X[low+2]);
dx=dist(X[low+1],X[low+2]);
if((dl<=dr)&&(dl<=d))
{
a=X[low];
b=X[low+1];
d=dl;
}
else
{
if(dr<=d)
{
a = X[low];
b = X[low+2];
d= dr;
}
else
{
a=X[low+1];
b=X[low+2];
d=dx;
}
}
}
else//當n>3時進行分治
{
A_POINT *SL=new A_POINT[(high-low)/2+1];
A_POINT *SR=new A_POINT[(high-low)/2];
m=(high-low)/2;//把x陣列以m為界劃分為兩半
j=k=0;
for(i=0;i<=high-low;i++)
{
if(Y[i].index<=m)
{
SL[j++]=Y[i];//收集左邊子集中的最近點對
}
else
{
SR[k++]=Y[i];//收集右邊子集中的最近點對
}
}
closest(X,SL,low,m,al,bl,dl);//計算左邊子集的最近點對
closest(X,SR,m+1,high,ar,br,dr);//計算右邊子集的最近點對
if(dl<dr)
{
a=al;b=bl;d=dl;
}
else
{
a=ar;b=br;d=dr;
}
POINT *Z=new POINT[high-low+1];
k=0;
for(i=0;i<=high-low;i++)//收集距離中線距離小于d的元素，保存到陣列Z中
{
if(fabs(X[m].x-Y[i].x)<d)
{
Z[k].x=Y[i].x;
Z[k++].y=Y[i].y;
}
}
for(i=0;i<k;i++)
{
for(j=i+1;(j<k)&&(Z[j].y-Z[i].y<d);j++)
dl=dist(Z[i],Z[j]);
if(dl<d)
{
a = Z[i];
b = Z[j];
d = dl;
}
}
}
//delete SL;
//delete SR;
//delete Z;
}
}
void closest_pair(POINT X[],int n,POINT &a,POINT &b,float &d)
{
if(n<2)
{
d=0;
}
else
{
sort(X,X+n, compareX); // 對x陣列進行遞增排序
A_POINT *Y = new A_POINT[n]; // 初始化輔助點陣列Y
for( int i = 0 ; i < n ;i ++)
{
Y[i].index = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
sort(Y,Y+n, compareY); // 對y陣列進行遞增排序
closest(X,Y,0,n-1,a,b,d); // 求親密點對
d = sqrt(d); // 將得到的d開平方才是兩點間真正的距離
delete Y;
}
}
int filearrayload(POINT *X)
{
int num1;
ifstream infile("data.txt", ios::in); //檔案改成了程式所在檔案夾（非必須）
if (!infile)
{
cout << "open file error!" << endl;
exit(1);
}
int i = 0;
for (i = 0; !infile.eof(); i++)
{
infile >> X[i].x >> X[i].y;
}
num1 = i;
infile.close();
return num1;
}
int main()
{
int n;
POINT *X=new POINT[n];
//n=filearrayload(X);
POINT a,b;
float d;
closest_pair(X,n,a,b,d);
if(n>=2)
{
cout<<"("<<a.x<<","<<a.y<<")"<<","<<"("<<b.x<<","<<b.y<<")"<<endl;
cout<<"最近點的距離為："<<d<<endl;
}
else
{
cout<<"不存在最近點對！"<<endl;
}
delete X;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/101655.html
標籤：基礎類
上一篇：鴻蒙不是Linux也不是安卓