算法笔记-----计算两点距离----O(n2)简单实现

  1 #include<stdlib.h>
  2 #include<stdio.h>
  3 #include<iostream>
  4 #include<math.h>
  5 #include<algorithm>
  6 #include <time.h>
  7 
  8 #define MAX 99999
  9 using namespace std;
 10 
 11 struct point{           //点结构
 12     double x,y;
 13 };
 14 
 15 double Distance(point a,point b){
 16     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 17 }
 18 bool cmp(point a,point b){          //按y升排序辅助函数
 19     return a.y<b.y;
 20 }
 21 bool cmp2(point a,point b){          //按x升排序辅助函数
 22     return a.x<b.x;
 23 }
 24 double closestPoint(point s[],int low,int high,point rec[]){
 25     double d1,d2,d3,d;
 26     int mid,i,j,index;
 27     double x1,y1,x2,y2;         //记录点对的位置
 28     point P[high-low+1],temp1[2],temp2[2],temp3[2];         //辅助空间
 29     if(high-low==1){             //两个点的情况
 30         rec[0].x=s[low].x;rec[0].y=s[low].y;
 31         rec[1].x=s[high].x;rec[1].y=s[high].y;
 32         return Distance(s[low],s[high]);
 33     }
 34     if(high-low==2){            //三个点的情况
 35         d1=Distance(s[low],s[low+1]);
 36         d2=Distance(s[low+1],s[high]);
 37         d3=Distance(s[low],s[high]);
 38         if((d1<d2)&&(d1<d3)){
 39             rec[0].x=s[low].x;rec[0].y=s[low].y;
 40             rec[1].x=s[low+1].x;rec[1].y=s[low+1].y;
 41             return d1;
 42         }
 43         else if(d2<d3){
 44             rec[0].x=s[low+1].x;rec[0].y=s[low+1].y;
 45             rec[1].x=s[high].x;rec[1].y=s[high].y;
 46             return d2;
 47         }
 48         else {
 49             rec[0].x=s[low].x;rec[0].y=s[low].y;
 50             rec[1].x=s[high].x;rec[1].y=s[high].y;
 51             return d3;
 52         }
 53     }
 54     mid=(low+high)/2;       //其他情况递归
 55     d1=closestPoint(s,low,mid,rec);
 56     temp1[0]=rec[0];
 57     temp1[1]=rec[1];
 58     d2=closestPoint(s,mid+1,high,rec);
 59     temp2[0]=rec[0];
 60     temp2[1]=rec[1];
 61     if(d1<d2){
 62         d=d1;
 63         rec[0]=temp1[0];
 64         rec[1]=temp1[1];
 65     }
 66     else {
 67         d=d2;
 68         rec[0]=temp2[0];
 69         rec[1]=temp2[1];
 70     }
 71     index=0;
 72     for(i=mid;(i>=low)&&((s[mid].x-s[i].x)<d);i--)      //点集合p1
 73         P[index++]=s[i];
 74     for(i=mid+1;(i<=high)&&((s[i].x-s[mid].x)<d);i++)      //点集合p2
 75         P[index++]=s[i];
 76     sort(P,P+index,cmp);                    //升序排列
 77     for(i=0;i<index;i++){
 78         for(j=j+1;j<index;i++){
 79             if((P[j].y-P[i].y)>=d)
 80                 break;
 81             else {
 82                 d3=Distance(P[i],P[j]);
 83                 if(d3<d){
 84                     rec[0].x=P[i].x;rec[0].y=P[i].y;
 85                     rec[1].x=P[j].x;rec[1].y=P[j].y;
 86                     d=d3;
 87                 }
 88             }
 89         }
 90     }
 91     return d;
 92 }
 93 
 94 //double closestPoints(double x[],double y[],int n){
 95 //    double x1,x2,y1,y2;                      //记录下标
 96 //    double dist,minDist=MAX;
 97 //    for(int i=0;i<n;i++)
 98 //        for(int j=i+1;j<n;j++){
 99 //            dist=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);       //计算距离
100 //            if(dist<minDist){
101 //                minDist=dist;
102 //                x1=x[i];y1=y[i];
103 //                x2=x[j];y2=y[j];
104 //            }
105 //        }
106 //    cout<<"最近点对为：("<<x1<<","<<y1<<")-("<<x2<<","<<y2<<")";      //输出坐标
107 //    return minDist;
108 //}
109 
110 
111 
112 int mainz(){
124 
125     point p[100];            //设定点的集合
126     int d=50;
127     srand((unsigned)time(NULL));
128     for(int i = 0; i < 25;i++ )
129     {
130         p[i].x = rand()%d+1;
131         p[i].y = rand()%d+1;
132         d++;
133         cout<<p[i].x<<"--"<<p[i].y<<"  ";
134     }
135     printf("
");
136     int n=25;
137     double minDist;
138 
139 //    cout<<"输入点的个数：
";      //输入点的个数
140 //    cin>>n;
141 //    cout<<"输入点集:（x,y）
";
142 //    for(int i=0;i<n;i++)
143 //        cin>>p[i].x>>p[i].y;
144 
145     sort(p,p+n,cmp2);
146     point index[2];
147     minDist=closestPoint(p,0,n-1,index);
148     cout<<"最小距离点对为：("<<index[0].x<<","<<index[0].y<<"),("<<index[1].x<<","<<index[1].y<<")
";
149     cout<<"最小距离为：
"<<minDist;      //输出点对的最小问题
150     return 0;
151 }