1. 问题
给定一个二维平面上的n个点p1(x1,y1),p2(x2,y2)…pn(xn,yn).求出其中最短的两点之间的距离
2. 解析
主要采用分治的思想来解决问题。首先将所有点根据x坐标进行排序。大问题的是求出n的点其中最短两点的距离，可以将n个点平分为两个集合，中间的点为mid，分别求两个集合中的点最短两点的距离dist1，dist2，并得到dist = min(dist1,dist2)。但是还可能存在一种情况，最短距离的两个点分别在两个集合中。因此在解决完两个小问题后还要进行判断。在得到前两个距离后，就可以对这个问题进行化简。判断所有满足pa(xa,ya),pb(xb,yb),使得xa属于[mid-dist,mid]，xb[mid,mid+dist]属于条件的两点的距离是否小于dist，并对dist进行更新。最后就可以得到dist。
3. 设计
findClosestPoint(tar,start,end)
{
Amount = end-start+1;
Mid = (start+end)/2;
Midvalue = (a[start].x+a[end].x)/2.0;
If(amount == 2)
Return start与end之间的距离;
Else if(amount == 1)
Return inf
Else
{
Dist1 = findClosestPoint(a,start,mid);
Dist2 = findClosestPoint(a,mid+1,end);
Dist = min(dist1,dist2);
Double thisdist = inf;
For(int I = start;I <= end;i++)
For(int j = start;j <= end;j++)
{
If(i.x属于[midvalue-dist,midvalue] && j.x属于[midvalue,midvalue+dist])
Dsi = I,j之间的距离
If(dis < thisdist)
Thisdist = dis;
}
}
Dist = mini(dist,thisdist);
Return dist;
}
4. 分析
