先介绍下二者的时间复杂度:
Andrew算法是葛立恒扫描法的变种,但是更快,时间O(nlogn)。
Melkman算法是采用双端队列,时间O(n)。
第一种是经典算法,第二种则是在解决时间要求高的问题上的一个也是目前我所知道最快的。
Andrew代码如下:
int Andrew(Point *p,int n,Point *q)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&Cross(q[m-1]-q[m-2],p[i]-q[m-2])<=0) m--;
q[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&Cross(q[m-1]-q[m-2],p[i]-q[m-2])<=0) m--;
q[m++]=p[i];
}
if(n>1) m--;
return m;
}
Melkman代码如下:
double Cross(Vector A,Vector B) { return A.x*B.y - A.y*B.x;}
double side(Point a,Point b,Point p)
{
Vector A=Vector(b.x-a.x,b.y-a.y);
Vector B=Vector(p.x-a.x,p.y-a.y);
return Cross(A,B);
}
void Melkman(int n,int &head,int &tail)
{
int i;
head=tail=n;
ch[tail++]=p[0];
for(i=0;i<n;i++)
{
ch[tail]=p[i];
if(side(ch[head],ch[head+1],p[i+1])) break;
}
if(n<3) return;
ch[++tail]=ch[--head]=p[++i];
if(side(ch[n],ch[n+1],ch[n+2])<0) swap(ch[n],ch[n+1]);
for(++i;i<n;i++)
{
if(side(ch[head+1],ch[head],p[i])<0&&
side(ch[tail-1],ch[tail],p[i])>0) continue;
while(tail-head>1&&side(ch[head+1],ch[head],p[i])>=0)
++head;
ch[--head]=p[i];
while(tail-head>1&&side(ch[side-1],ch[tail],p[i])<=0)
--tail;
ch[++tail]=p[i];
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)