HDU-1007 Quoit Design 最小距离点对

2024-06-16 16:38
文章标签 design 最小 距离 hdu 1007 quoit

本文主要是介绍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点之间的距离才会小于δ,最小点对计算才有意义。

    

 

Figure 2

 

 

      对于SL虚框范围内的p点,在SR虚框中与p点距离小于δ的顶多只有六个点,就是图二右图中的2个正方形的6的顶点。这个可以反推证明,如果右边这2个正方形内有7个点与p点距离小于δ,例如q点,则q点与下面正方形的四个顶点距离小于δ,则和δSLSR的最小点对距离相矛盾。因此对于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 最小距离点对的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1066974

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl