首页 / 算法 / 算法分析与设计——最近点对问题
算法分析与设计——最近点对问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法分析与设计——最近点对问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2102字，纯文字阅读大概需要4分钟。
内容图文
算法分析与设计——最近点对问题
题目
这个题目目前对于大家会有点难度，有兴趣的同学可以研究一下，这种题目才是分治的精髓所在。
前段时间 partychen 到吴泾去买东西，发现在步行街有一个赌博游戏，一个商人在地面上摆放了很多的小礼品，然后准备了很多大小相同的圆环，玩家可以到商人处花 5 块钱买一个圆环。然后站在一根白线外使用圆环套住自己想要的礼品。圆环套住的东西就归玩家所有。我这里描述的不是很清楚，但是我相信大家肯定也知道这个是什么游戏了。
出于商人的本性，他现在想邀请计算机的你，帮助他设计一个圆环，使得这个圆环最多只能套住一个小礼品。
为了让问题简单化，我们假设每一个小礼品都是平面上的一个点。如果点在圆环上也算套住。当然如果两个礼品重叠放置的话 那么圆环的半径显然会是 0。
他只要你求出这个圆环的半径。
输入
输入数据有多组，每组测试数据第一行有一个正整数 N (2≤N≤100000), 表示平面上有多少个点。然后有 N 组实数对 (x,y) (?1000≤x,y≤1000) 表示点的坐标。如果 N=0 表示输出结束，并且不作处理。
输出
对于每组测试数据，输出圆环的半径，结果保留两位小数。每个输出占一行。
样例
问题分析
所求的圆环最小半径实际上是给定点集的最近距离的一半，因此只要遍历点集计算所有点对之间的距离，找到最小距离即可。假设有n个点，如果挨个计算所有点对之间的距离，则需要的时间为 Θ(n*(n-1)/2) 。如果采用分治策略，将点集分为左半部分 (l,mid) 和右半部分 (mid+1,r) ，分别计算出两部分的最近点对距离 minl 和 minr，再找到分别从左半部分和右半部分各取一个点组成的点对的最近距离min，最近点对距离就是这三个值中的最小值。这种情况下，T(n) = 2*T(n/2)+n^2/4 = … = 2n+1/2n^2。（欸欸欸？变多了？…先不管吧）
代码
double min_dist(int l, int r)
{
if(l == r)
return 8000001;//最远点对距离的平方为8000000
if(l == r-1)
return sqrt((points[l][0]-points[r][0])*(points[l][0]-points[r][0])+(points[l][1]-points[r][1])*(points[l][1]-points[r][1]));
int mid = (l+r)/2;
double minl = min_dist(l,mid);
double minr = min_dist(mid+1,r);
int i,j;
double min = 8000001,tmp;
for(i = l; i <= mid; i++)
{
for(j = mid+1; j <= r; j++)
{
tmp = (points[i][0]-points[j][0])*(points[i][0]-points[j][0])+(points[i][1]-points[j][1])*(points[i][1]-points[j][1]);
if(tmp < min)
min = tmp;
}
}
min = sqrt(min);
min = min>minl ? minl : min;
min = min>minr ? minr : min;
return min;
}
内容总结
以上是互联网集市为您收集整理的算法分析与设计——最近点对问题全部内容，希望文章能够帮你解决算法分析与设计——最近点对问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。