问题
给定平面上N个点的坐标,找出距离最远的两个点。
分析
类似于“最近点对问题”,这个问题也可以用枚举的方法求解,时间复杂度O(n^2)。
“寻找最近点对”是用到分治策略降低复杂度,而“寻找最远点对”可利用几何性质。注意到:对于平面上有n个点,这一对最远点必然存在于这n个点所构成的一个凸包上(证明略),那么可以排除大量点,如下图所示:
在得到凸包以后,可以只在顶点上面找最远点了。同样,如果不O(n^2)两两枚举,可以想象有两条平行线, “卡”住这个凸包,然后卡紧的情况下旋转一圈,肯定就能找到凸包直径,也就找到了最远的点对。或许这就是为啥叫“旋转卡壳法”。
总结起来,问题解决步骤为:
1、用Graham's Scanning求凸包
2、用Rotating Calipers求凸包直径,也就找到了最远点对。
该算法的平均复杂度为O(nlogn) 。最坏的情况下,如果这n个点本身就构成了一个凸包,时间复杂度为O(n^2)。
旋转卡壳可以用于求凸包的直径、宽度,两个不相交凸包间的最大距离和最小距离等。虽然算法的思想不难理解,但是实现起来真的很容易让人“卡壳”。
逆向思考,如果qa,qb是凸包上最远两点,必然可以分别过qa,qb画出一对平行线。通过旋转这对平行线,我们可以让它和凸包上的一条边重合,如图中蓝色直线,可以注意到,qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边,对每一条边找出凸包上离该边最远的顶点,计算这个顶点到该边两个端点的距离,并记录最大的值。直观上这是一个O(n2)的算法,和直接枚举任意两个顶点一样了。但是注意到当我们逆时针枚举边的时候,最远点的变化也是逆时针的,这样就可以不用从头计算最远点,而可以紧接着上一次的最远点继续计算,于是我们得到了O(n)的算法。
http://poj.org/problem?id=2187
// 求最远点对
#include<iostream>
#include<algorithm>
using namespace std;
struct point
{
int x , y;
}p[50005];
int top , stack[50005]; // 凸包的点存在于stack[]中
inline double dis(const point &a , const point &b)
{
return (a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y);
}
inline int max(int a , int b)
{
return a > b ? a : b;
}
inline int xmult(const point &p1 , const point &p2 , const point &p0)
{ //计算叉乘--线段旋转方向和对应的四边形的面积--返回(p1-p0)*(p2-p0)叉积
//if叉积为正--p0p1在p0p2的顺时针方向; if(x==0)共线
return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x);
}
int cmp(const void * a , const void * b) //逆时针排序 返回正数要交换
{
struct point *p1 = (struct point *)a;
struct point *p2 = (struct point *)b;
int ans = xmult(*p1 , *p2 , p[0]); //向量叉乘
if(ans < 0) //p0p1线段在p0p2线段的上方,需要交换
return 1;
else if(ans == 0 && ( (*p1).x >= (*p2).x)) //斜率相等时,距离近的点在先
return 1;
else
return -1;
}
void graham(int n) //形成凸包
{
qsort(p+1 , n-1 , sizeof(point) , cmp);
int i;
stack[0] = 0 , stack[1] = 1;
top = 1;
for(i = 2 ; i < n ; ++i)
{
while(top > 0 && xmult( p[stack[top]] , p[i] , p[stack[top-1]]) <= 0)
top--; //顺时针方向--删除栈顶元素
stack[++top] = i; //新元素入栈
}
int temp = top;
for(i = n-2 ; i >= 0 ; --i)
{
while(top > temp && xmult(p[stack[top]] , p[i] , p[stack[top-1]]) <= 0)
top--;
stack[++top] = i; //新元素入栈
}
}
int rotating_calipers() //卡壳
{
int i , q=1;
int ans = 0;
stack[top]=0;
for(i = 0 ; i < top ; i++)
{
while( xmult( p[stack[i+1]] , p[stack[q+1]] , p[stack[i]] ) > xmult( p[stack[i+1]] , p[stack[q]] , p[stack[i]] ) )
q = (q+1)%(top);
ans = max(ans , max( dis(p[stack[i]] , p[stack[q]]) , dis(p[stack[i+1]] , p[stack[q+1]])));
}
return ans;
}
int main(void)
{
int i , n , leftdown;
while(scanf("%d",&n) != EOF)
{
leftdown = 0;
for(i = 0 ; i < n ; ++i)
{
scanf("%d %d",&p[i].x,&p[i].y);
if(p[i].y < p[leftdown].y || (p[i].y == p[leftdown].y && p[i].x < p[leftdown].x)) //找到最左下角的点
leftdown = i;
}
swap(p[0] , p[leftdown]);
graham(n);
printf("%d\n",rotating_calipers());
}
return 0;
}
分享到:
相关推荐
对给定的一副图像含有 不同目标 确定每一个目标的质心 坐标 及其最远点中心距
提出了一种确定点集最远点对的最优算法对平面内n个点的点集, 在求出其凸包后, 利用求对跖点对的方法确定凸包的最远点对, 从而得到点集的最远点对整个算法的时间复杂性为O(nlogn).
基于快速行进最远点的点云精简算法研究,严成,朱昊,在逆向工程中,冗余数据会影响三维重建效率,因此对原始数据进行精简非常重要。本文提出一种点云精简算法,采用快速行进最远点采
【点云处理】Python+Open3D实现最远点采样FPS(Farthest Point Sampling) 该方法被用于PointNet++中,对点云进行降采样,此外open3D自身有半径滤波、体素降采样等函数。 讲解为个人整理版本,程序已跑通。
给远点亲人的一封信参考.doc
给远点亲人的一封信参考精选.doc
深度学习:从“原点”走向“远点”.pdf
使用此文件,您可以找到一个空间基准,到最远点的距离最小。 您可以使用功能FMINIMAX完成项目,然后直接查看图像。
百度搜索圈住小猫就有很多网页可以在线玩了,很有趣的一个小游戏
百度搜索圈住小猫,捉猫猫就有很多网页可以在线玩,很有趣的一个小游戏,这个是他的源代码,喜欢的可以拿去研究研究
研究了一类含常数项和全二次项的三次多项式系统的无穷远点的中心与等时中心问题。通过同胚变换,三次实多项式系统的无穷远点转化为原点,研究三次系统的无穷远点的性质可以转化为研究系统原点的性质。通过复变换把实...
总结很全的Latex 数学符号,方便大家在用latex写论文时,查找符号,并给出了相应的公式例子,非常适合初学者。是个不错的小工具。
通过同胚变换把系统无穷远点化为原点,研究了一类五次系统无穷远点中心与拟等时中心问题。利用最新算法求出了无穷远点作为中心时的周期常数,给出并证明了这类五次系统无穷远点拟等时中心的条件。
研究了一类三次多项式系统无穷远点的奇点量与中心条件,用一同胚变换将无穷远点转变成原点(初等奇点),用计算机代数系统 Mathematica计算了这个多项式系统无穷远点的前 18个奇点量,并得到了无穷远点的中心条件和 18阶...
运用一种间接的方法研究了一类五次平面多项式系统无穷远点的极限环分支问题。首先将该问题转换成在原点的极限环分支问题,然后通过奇点量的计算,推导出系统在原点(无穷远点)的最高阶细焦点的条件。首次证明了五次...
首先,寻找一个投影矩阵H' 将右图的对极点e'映射到无穷远点,此时该图上的对极线被映射为平行于x轴的直线;然后,基于娇正后立体像对的对应极线相同的原理,推导出应用在左图上的矫正矩阵H;最后,根据得到的投影矩阵H和H'...
前者通过不断改变扫描线的倾斜角来寻找切点坐标, 并对无 效切点进行滤除,然后使用 Kasa 圆拟合法求取有效圆域的参数。后者则对传统柱面投影的光路进行了人为的弯折, 从而把投影到无穷远点的光线压缩回柱面上,...
本文讨论了复调和函数在无穷远点的性质,揭示出有界区城上复调和函数的两类表示式之间的关系。
它返回一个数组,其中每一行包含这些值 - [起点,终点,最远点,到最远点的近似距离]。如果为False,则查找该点是在内部还是外部或在轮廓上(它分别返回+1,-