算法导论求n个点的最小距离算法导论求n个点的最小距离
2010-01-20 17:23
在中文算法导论649页算法： 0：把所有的点按照横坐标排序 1：用一条竖直的线L将所有的点分成两等份 2：递归算出左半部分的最近两点距离d1，右半部分的最近两点距离d2，取d=min(d1,d2) 3：算出“一个在左半部分，另一个在右半部分”这样的点对的最短距离d3。 4：结果＝min(d1,d2,d3) 关键就是这第3步。貌似这需要n^2的时间，把左边每个点和右边每个点都对比一下。其实不然。秘密就在这里。 首先，两边的点，与分割线L的距离超过d的，...
算法导论求n个点的最小距离
2010-01-20 17:23
在中文算法导论649页算法： 0：把所有的点按照横坐标排序 1：用一条竖直的线L将所有的点分成两等份 2：递归算出左半部分的最近两点距离d1，右半部分的最近两点距离d2，取d=min(d1,d2) 3：算出“一个在左半部分，另一个在右半部分”这样的点对的最短距离d3。 4：结果＝min(d1,d2,d3) 关键就是这第3步。貌似这需要n^2的时间，把左边每个点和右边每个点都对比一下。其实不然。秘密就在这里。 首先，两边的点，与分割线L的距离超过d的，都可以扔掉了。 其次，即使两个点P1,P2（不妨令P1在左边，P2在右边）与分割线L的距离（水平距离）都小于d，如果它们的纵坐标之差大于d，也没戏。 就是这两点使得搜索范围大大减小： 对于左半部分的，与L的距离在d之内的，每个P1来说：右半部分内，符合以上两个条件的点P2最多只有6个！ 原因就是： d是两个半平面各自内，任意两点的最小距离，因此在同一个半平面内，任何两点距离都不可能超过d。 我们又要求P1和P2的水平距离不能超过d，垂直距离也不能超过d，在这个d*2d的小方块内，最多只能放下6个距离不小于d的点。 因此，第3步总的比较距离的次数不超过n*6。 第3步的具体做法是： 3.1 删除所有到L的距离大于d的点。 O(n) 3.2 把右半平面的点按照纵坐标y排序。 O(nlogn) 3.3 对于左半平面内的每个点P1，找出右半平面内纵坐标与P1的纵坐标的差在d以内的点P2，计算距离取最小值，算出d3。 O(n*6) = O(n) 因为3.2的排序需要O(nlogn)， 所以整个算法的复杂度就是O(n((logn)^2))。 改进： 我们对3.2这个排序的O(nlogn)不太满意。 既然整个算法是递归的，我们可以利用第2步的子递归中已经排好序的序列，在第3.2部归并这两个子列，这样3.2的复杂度变成了O(n)。 这样，整个算法就是O(nlogn)的。
代码如下: VC6.0下编译通过
#include "stdafx.h"#include #include #include #define MAX 10000
typedef struct point{int x,y;}POINT;double delta = MAX ;int totalnum;POINT mem_p1,mem_p2;
int cmx(const void *a,const void *b) //比较x坐标{return ((POINT *)a)->x-((POINT *)b)->x;}int cmy(const void *a,const void *b) //比较y坐标{return ((POINT *)a)->y-((POINT *)b)->y;}double min(double p1,double p2){return p1>p2?p2:p1;}double dist(POINT s1,POINT s2) //求两点的距离{double dx = s1.x-s2.x;double dy = s1.y-s2.y;return sqrt(dx*dx + dy*dy);}void rec_cl_pair(POINT a[],int i,int j){double temp,xx;int k;if(j-i<3)//小于或等于三个点的时候可以直接求得最小距离{qsort(a+i,j-i+1,sizeof(a[0]),cmy);//按Y坐标从小到大排列xx = dist(a[i],a[i+1]);//两个点的距离if(j-i==1)//只有两个点的时候直接返回{if(xxmiddle-delta && a[k].x < middle+ delta){t++;v[t] = a[k];//存入离中线距离小于delta的点}} //t-1为剩余点的个数qsort(v+1,t,sizeof(v[1]),cmy);//以Y坐标的大小进行排序for(k=1;k
本文档为【算法导论求n个点的最小距离】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483