幾何学的な凸包を計算するアルゴリズムAndrewとMelkmanアルゴリズム

まず二人の時間の複雑さを紹介します.
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;i1&&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;i0) 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];
  }
}