本文主要是介绍HDU-1007 Quoit Design 最小距离点对,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
求平面内任意两点间距离
1.蛮力法( 时间复杂度O(n^2) 适用于点的数目比较小的情况下)
算法描述:已知集合S中有n个点,一共可以组成n(n-1)/2对点对,蛮力法就是对这n(n-1)/2对点对逐对进行距离计算,通过循环求得点集中的最近点对:
2、分治法( 时间复杂度O(nlogn) )
1)算法描述:已知集合S中有n个点,分治法的思想就是将S进行拆分,分为2部分求最近点对。算法每次选择一条垂线L,将S拆分左右两部分为SL和SR,L一般取点集S中所有点的中间点的x坐标来划分,这样可以保证SL和SR中的点数目各为n/2,
(否则以其他方式划分S,有可能导致SL和SR中点数目一个为1,一个为n-1,不利于算法效率,要尽量保持树的平衡性)
依次找出这两部分中的最小点对距离:δL和δR,记SL和SR中最小点对距离δ = min(δL,δR),如图1:
以L为中心,δ为半径划分一个长带,最小点对还有可能存在于SL和SR的交界处,如下图2左图中的虚线带,p点和q点分别位于SL和SR的虚线范围内,在这个范围内,p点和q点之间的距离才会小于δ,最小点对计算才有意义。

对于SL虚框范围内的p点,在SR虚框中与p点距离小于δ的顶多只有六个点,就是图二右图中的2个正方形的6的顶点。这个可以反推证明,如果右边这2个正方形内有7个点与p点距离小于δ,例如q点,则q点与下面正方形的四个顶点距离小于δ,则和δ为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点,不需求出p点和右边虚线框内所有点距离,只需计算SR中与p点y坐标距离最近的6个点,就可以求出最近点对,节省了比较次数。
(否则的话,最坏情形下,在SR虚框中有可能会有n/2个点,对于SL虚框中的p点,每次要比较n/2次,浪费了算法的效率)
#include<stdio.h>
#include<queue>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 100005;
const int inf = 1<<30;
int n;
int temp[maxn]; //临时数组
struct node
{double x,y;
}point[maxn];
bool cmp( node a,node b )
{return a.x < b.x;
}
bool cmp1( int a,int b )
{return point[a].y > point[b].y;
}
double getDis( node a,node b ) //求距离
{return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double Min( double a,double b )
{return a < b?a:b;
}
double DFS( int ld,int rd )
{if( ld + 1 == rd ) //递归到两个点时最小距离为两点距离return getDis( point[ld],point[rd] );if( ld + 2 == rd ){ //区间内三个点时直接比较double a = getDis( point[ld], point[ld+1] );double b = getDis( point[ld+1], point[rd] );double c = getDis( point[ld], point[rd] );return Min( a,Min(b,c) );}int mid = (ld+rd)>>1;double minDis = Min( DFS( ld,mid ),DFS( mid+1,rd ) ); //回带最小距离//比较一个点在左边 一个点在右边的最小距离int k = 0;for( int i = ld; i <= rd; i ++ ){ //在区间内找出x坐标不超过minDis的点if( point[i].x >= point[mid].x - minDis && point[i].x <= point[mid].x + minDis){temp[k++] = i;}}sort( temp,temp+k,cmp1 ); //对这些点排序 截枝比较最小距离for( int i = 0; i < k; i ++ ) //比较{for( int j = i+1; j < k; j ++ ){if( point[temp[i]].y - point[temp[j]].y > minDis ) //截枝break;minDis = Min( minDis,getDis( point[temp[i]],point[temp[j]] ) );}}return minDis;
}
int main()
{//freopen( "data.txt","r",stdin );while( scanf("%d",&n) != EOF,n ){ for( int i = 0; i < n; i ++ )scanf("%lf%lf",&point[i].x,&point[i].y);sort( point,point+n,cmp );printf("%.2lf\n",DFS(0,n-1)/2 );}return 0;
}
这篇关于HDU-1007 Quoit Design 最小距离点对的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!