posts - 74,  comments - 33,  trackbacks - 0

给定n 个点(xi,yi)(1≤i≤n),要求找出其中距离最近的两个点。

例14-7 假设在一片金属上钻n 个大小一样的洞,如果洞太近,金属可能会断。若知道任意两个洞的最小距离,可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。

通过检查所有的n(n- 1 ) / 2对点,并计算每一对点的距离,可以找出距离最近的一对点。这种方法所需要的时间为(n2 )。我们称这种方法为直接方法。图1 4 - 1 3中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解,而对于大的问题则首先把它划分为两个较小的问题,其中一个问题(称为A)的大小为「n /2ù,另一个问题(称为B)的大小为「n /2ù。初始时,最近的点对可能属于如下三种情形之一: 1) 两点都在A中(即最近的点对落在A中);2) 两点都在B中;3) 一点在A,一点在B。假定根据这三种情况来确定最近点对,则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解,而在第二种情况下可对B进行递归求解。


if (n较小) {用直接法寻找最近点对

R e t u r n ; }

// n较大

将点集分成大致相等的两个部分A和B

确定A和B中的最近点对

确定一点在A中、另一点在B中的最近点对

从上面得到的三对点中,找出距离最小的一对点

图14-13 寻找最近的点对


为了确定第三种情况下的最近点对,需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi(中间值)处划一条垂线,线左边的点属于A,线右边的点属于B。位于垂线上的点可在A和B之间分配,以便满足A、B的大小。

例2-8 考察图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1,垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A,右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上,可将其中两个加入A, 另一个加入B,以便A、B中包含相同的点数。假设d ,m加入A,g加入B。

设是i 的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于,这样,就可以淘汰那些距垂线距离≥ 的点。图1 4 - 1 5中的虚线是分割线。阴影部分以分割线为中线,宽为2 。边界线及其以外的点均被淘汰掉,只有阴影中的点被保留下来,以便确定是否存在第三类点对(对应于第三种情况)其距离小于。用RA、RB 分别表示A和B中剩下的点。如果存在点对(p,q),p?A, q?B且p, q 的距离小于,则p?RA,q?RB。可以通过每次检查RA 中一个点来寻找这样的点对。假设考察RA 中的p 点,p的y 坐标为p.y,那么只需检查RB 中满足p.y- <q.y<p.y+ 的q 点,看是否存在与p 间距小于的点。在图14-16a 中给出了包含这种q 点的RB 的范围。因此,只需将RB 中位于×2 阴影内的点逐个与p 配对,以判断p 是否是距离小于的第三类点。这个×2 区域被称为是p 的比较区(comparing region)。

例2-9 考察例2 - 8中的1 4个点。A中的最近点对为(b,h),其距离约为0 . 3 1 6。B中最近点对为(f, j),其距离为0 . 3,因此= 0 . 3。当考察是否存在第三类点时,除d, g, i, l, m 以外的点均被淘汰,因为它们距分割线x= 1的距离≥ 。RA ={d, i, m},RB= {g, l},由于d 和m 的比较区中没有点,只需考察i即可。i 的比较区中仅含点l。计算i 和l的距离,发现它小于,因此(i, l) 是最近的点对。

为了确定一个距离更小的第三类点,RA 中的每个点最多只需和RB 中的6个点比较,如图1 4 - 1 6所示。

1. 选择数据结构

为了实现图1 4 - 1 3的分而治之算法,需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对,因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”,就可以避免产生少于两点的点集。

每个点可有三个参数:标号, x 坐标,y 坐标。假设标号为整数,每个点可用P o i n t l类(见程序1 4 - 8)来表示。为了便于按x 坐标对各个点排序,可重载操作符<=。归并排序程序如1 4 -3所示。

程序14-8 点类

class Point1 {

friend float dist(const Point1&, const Point1&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&,float&);

friend void main();

p u b l i c :

int operator<=(Point1 a) const

{return (x <= a.x);}

p r i v a t e :

int ID; // 点的编号

float x, y; // 点坐标

} ;

class Point2 {

friend float dist(const Point2&, const Point2&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&, float&);

friend void main();

p u b l i c :

int operator<=(Point2 a) const

{return (y <= a.y);}

p r i v a t e :

int p; // 数组X中相同点的索引

float x, y; // 点坐标

} ;

所输入的n 个点可以用数组X来表示。假设X中的点已按照x 坐标排序,在分割过程中如果当前考察的点是X [l :r],那么首先计算m= (l+r) / 2,X[ l:m]中的点属于A,剩下的点属于B。计算出A和B中的最近点对之后,还需要计算RA 和RB,然后确定是否存在更近的点对,其中一点属于RA,另一点属于RB。如果点已按y 坐标排序,那么可以用一种很简单的方式来测试图1 4 - 1 6。按y 坐标排序的点保存在另一个使用类P o i n t 2 (见程序14-8) 的数组中。注意到在P o i n t 2类中,为了便于y 坐标排序,已重载了操作符<=。成员p 用于指向X中的对应点。

算法设计与分析
第二章——分治
#include  < algorithm >  
#include 
< iostream >  
#include 
< cmath >  
using namespace std; 
#define abst(a,b) (a>b?(a-b):(b-a)) 
typedef double TYPE; 
#define Abs(x) ((x)>0 ? (x) : -(x)) 
#define Sgn(x) ((x)
< ? (-1) : (1)) 
#define Max(a,b) ((a)
> (b) ? (a) : (b)) 
#define Min(a,b) ((a)
< (b ) ? (a) : (b)) 
#define Epsilon 1e-8 
#define Infinity 1e10 
const double PI
=acos(-1.0); 

struct MPOINT { 
    MPOINT(int xx
=0,int  yy =0,int  tt =0):x(xx),y(yy),type(tt){} 
    
int x; 
    int y; 
    int type; 
}; 
MPOINT point[1000010]; 
double result; 
bool cmp(MPOINT s,MPOINT t) 

    return s.x<t.x; 

double len(MPOINT& a,MPOINT& b) 

    return sqrt(double(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y))); 

double mergepoint(int l,int r) 

    double resultl
=0,resultr=0,minlen=1000000000; 
    
if(r > l+4) { 
        int mid=(l+r)>>1; 
        double tempdis; 
        resultl=mergepoint(l,mid); 
        resultr=mergepoint(mid,r); 
        minlen=min(resultl,resultr); 
        for(int i=mid;i>=l&
&point [i].x>point[mid].x-minlen;i--) { 
            for(int j=mid;j
< =r &&point[j].x<point[mid].x+minlen;j++) { 
                if(point[i].type!
=point[j].type&&abst(point[j].y,point[mid].y)<minlen) 
                    tempdis
=len(point[i],point[j]); 
                    
if(tempdis<minlen) { 
                        minlen
=tempdis; 
                    

                } 
            } 
        } 
    } 
    else 
    { 
        double distemp; 
        for(int i
=l;i<r;i++) 
            for(int j
=l+1;j<=r;j++) 
                if(j
==i) 
                    continue; 
                } 
                if(point[i].type!
=point[j].type) 
                    distemp
=len(point[i],point[j]); 
                    
minlen =minlen>distemp?distemp:minlen; 
                

            } 
        } 
    } 
    return minlen; 

int input() 

    int n; 
    scanf("%d",&n); 
        for(int i
=0;i<n;i++) 
            scanf("%d%d",&point[i].x,&point[i].y); 
            point[i].type
=0; 
        

        for(int i
=n;i<(n<<1);i++) 
            scanf("%d%d",&point[i].x,&point[i].y); 
            point[i].type
=1; 
        

        return n; 

int main() 

    int cas,n,x,y; 
    scanf("%d",&cas); 
    while(cas--) { 
        result
=0; 
        
n =input(); 
        
sort(&point[0],&point[n<<1],cmp); 
        double result
=mergepoint(0,(n<<1)-1); 
        
printf("%.3lf\n",result); 
    } 
    return 1; 

posted on 2009-01-04 20:04 KNIGHT 阅读(2727) 评论(1)  编辑 收藏 引用

FeedBack:
# 插入排序的TOP-DOWN
2009-05-28 22:31 | aa
q
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜