寻找最近点对

fcpp.h

  1 #ifndef FCCP_H
  2 #define FCCP_H
  3 
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <math.h>
  7 #include <malloc.h>
  8 
  9 typedef int ElemType;
 10 
 11 ElemType position(ElemType a[],ElemType b[],int start,int end);
 12 
 13 void swap(ElemType &a,ElemType &b)
 14 {
 15     ElemType temp;
 16     temp = a;
 17     a = b;
 18     b = temp;
 19 }
 20 
 21 void sortTwo(ElemType a[],ElemType b[],int start,int end)//使用快速排序实现对a的排序，其中保持b中元素位置相对于a不变
 22 {
 23     if(start < end)
 24     {
 25         int pos = position(a,b,start,end);
 26         sortTwo(a,b,start,pos-1);
 27         sortTwo(a,b,pos+1,end);
 28     }
 29 }
 30 
 31 ElemType position(ElemType a[],ElemType b[],int start,int end)//快速排序求划分位置方法
 32 {
 33     ElemType temp = a[start],temp2 = b[start];
 34     int i = start,j = end;
 35 
 36     while(i < j)
 37     {
 38         while(j > i && a[j] >= temp) 
 39         {
 40             j--;
 41         }
 42         if(i < j)
 43         {
 44             a[i] = a[j];
 45             b[i] = b[j];
 46         }
 47         while(j > i && a[i] <= temp)
 48         {
 49             i++;
 50         }
 51         if(i < j)
 52         {
 53             a[j] = a[i];
 54             b[j] = b[i];
 55         }
 56     }
 57     a[i] = temp;
 58     b[i] = temp2;
 59     return i;
 60 }
 61 
 62 void sort(ElemType a[],ElemType b[],int n)//对按照a排序后中a值相同的情况再按照b中元素的大小进行排序
 63 {
 64     for(int i = 0;i < n-1;)
 65     {
 66         int s,e;
 67         while(a[i] != a[i+1] && i < n-1)
 68         {
 69             i++;
 70         }
 71         s = i;
 72         while(a[i] == a[i+1] && i < n-1)
 73         {
 74             i++;
 75         }
 76         e = i;
 77         for(int j = s;j <= e;j++)
 78         {
 79             for(int m = e-s+j;m > j;m--)
 80             {
 81                 if(b[m] < b[m-1])
 82                 {
 83                     swap(b[m],b[m-1]);
 84                 }
 85             }
 86         }
 87         i++;
 88     }
 89 }
 90 
 91 //---fccp是求解n个点中距离最小的2个点的距离和点的坐标
 92 void fccp(int start,int end,ElemType x[],ElemType y[],ElemType idn[],double &minLen,ElemType &px,ElemType &py,ElemType &qx,ElemType &qy)
 93 {
 94     int m = end-start+1;//每一步都要判断准确，是大的减去小的才行
 95     qx = qy = px = py = 0;
 96     if(m <= 3)//m<=3的情况
 97     {
 98         minLen = 10000;
 99         for(int i = 0;i < m-1;i++)
100         {
101             for(int j = i+1;j <= m-1;j++)
102             {
103                 int ylen = y[j]-y[i];
104                 int xlen = x[idn[j]] - x[idn[i]];
105                 xlen = xlen > 0 ? xlen : -xlen;
106                 double mlen = sqrt((double)(ylen*ylen+xlen*xlen));
107                 if(minLen > mlen)
108                 {
109                     minLen = mlen;
110                     px = x[idn[i]];
111                     py = y[i];
112                     qx = x[idn[j]];
113                     qy = y[j];
114                 }
115             }
116         }
117     }
118     else//m>=4的情况
119     {
120         ElemType *YL,*IDNL,*YR,*IDNR;
121 
122         int r = m/2;//右边数组长度
123         int l = m-r;//左边数组长度
124         int lengthL = 0;
125         int lengthR = 0;
126 
127         YL = (ElemType *)malloc(sizeof(ElemType)*l);
128         IDNL = (ElemType *)malloc(sizeof(ElemType)*l);
129         YR = (ElemType *)malloc(sizeof(ElemType)*r);
130         IDNR = (ElemType *)malloc(sizeof(ElemType)*r);
131 
132         for(int i = 0;i < m;i++)
133         {
134             if(idn[i] <= start+l-1)
135             {
136                 YL[lengthL] = y[i];
137                 IDNL[lengthL] = idn[i];
138                 lengthL++;
139             }
140             else
141             {
142                 YR[lengthR] = y[i];
143                 IDNR[lengthR] = idn[i];
144                 lengthR++;
145             }
146         }
147 
148         double mlenl,mlenr;
149         ElemType qxl,qxr,qyl,qyr,pxl,pxr,pyl,pyr;
150 
151         fccp(start,start+l-1,x,YL,IDNL,mlenl,pxl,pyl,qxl,qyl);
152         fccp(start+l,end,x,YR,IDNR,mlenr,pxr,pyr,qxr,qyr);
153 
154         if(mlenl < mlenr)
155         {
156             minLen = mlenl;
157             px = pxl;
158             py = pyl;
159             qx = qxl;
160             qy = qyl;
161         }
162         else
163         {
164             minLen = mlenr;
165             px = pxr;
166             py = pyr;
167             qx = qxr;
168             qy = qyr;
169         }
170 
171         double xdiv = (double)(x[start+l-1]+x[start+l])/2;//求分割线
172 
173         ElemType *YC,*IDNC;
174         YC = (ElemType *)malloc(sizeof(ElemType)*m);
175         IDNC = (ElemType *)malloc(sizeof(ElemType)*m);
176         int lengthC = 0;
177 
178         for(int i = 0;i < m;i++)
179         {
180             if(x[idn[i]] > xdiv-minLen && x[idn[i]] < xdiv+minLen)
181             {
182                 YC[lengthC] = y[i];
183                 IDNC[lengthC] = idn[i];
184                 lengthC++;
185             }
186         }
187 
188         if(lengthC <= 0)
189         {
190             return;
191         }
192 
193         for(int i = 0;i < lengthC-1;i++)
194         {
195             ElemType ypres = y[i];
196             ElemType xpres = x[IDNC[i]];
197             int u = (i+4) > lengthC-1 ? lengthC-1 : (i+4);//u是检查的最大下标
198             int v = i+1;
199             while(v <= u && YC[v]-ypres < minLen)
200             {
201                 ElemType tempYlen = YC[v]-ypres;
202                 ElemType tempXlen = x[IDNC[v]] - xpres;
203                 tempXlen = tempXlen>0 ? tempXlen : -tempXlen;
204                 double tempLen = sqrt((double)(tempXlen*tempXlen+tempYlen*tempYlen));
205                 if(tempLen < minLen)
206                 {
207                     minLen = tempLen;
208                     px = xpres;
209                     py = ypres;
210                     qx = x[IDNC[v]];
211                     qy = YC[v];
212                 }
213                 v++;
214             }
215         }
216     }
217 }
218 
219 #endif

main.cpp

 1 #include "fcpp.h"
 2 
 3 int main()
 4 {
 5     //这里先测试数据可以重复，x相同的情况下按照y从小到大排列
 6     int x[8] = {1,9,3,4,6,7,2,8};
 7     int y[8] = {5,6,8,12,1,7,4,9};
 8     int idn[8] = {0,1,2,3,4,5,6,7};
 9 
10     sortTwo(x,y,0,7);
11     sort(x,y,8);
12 
13     /*
14     for(int i = 0;i < 8;i++)
15     {
16         printf("%d ",x[i]);
17     }
18     printf("\n");
19     for(int i = 0;i < 8;i++)
20     {
21         printf("%d ",y[i]);
22     }
23     printf("\n");
24     for(int i = 0;i < 8;i++)
25     {
26         printf("%d ",idn[i]);
27     }
28     printf("\n");
29     */
30 
31     sortTwo(y,idn,0,7);
32 
33     /*
34     for(int i = 0;i < 8;i++)
35     {
36         printf("%d ",x[i]);
37     }
38     printf("\n");
39     for(int i = 0;i < 8;i++)
40     {
41         printf("%d ",y[i]);
42     }
43     printf("\n");
44     for(int i = 0;i < 8;i++)
45     {
46         printf("%d ",x[idn[i]]);
47     }
48     printf("\n");
49     */
50 
51     ElemType px,py,qx,qy;
52     double minLen;
53 
54     fccp(0,7,x,y,idn,minLen,px,py,qx,qy);
55 
56     printf("the shortest length between the two points is : %lf\n\n",minLen);
57     printf("the point is ( %d , %d ) and ( %d , %d )",px,py,qx,qy);
58 
59     system("pause");
60     return 0;
61 }