Documentation/graham_scan.by_leehark.cpp

   1 //written by leehark
   2 //any problem please send mail to me: lihe21327@gmail.com (also gtalk)
   3
   4 double det(point a,point b,point c)
   5 {return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
   6 double dis(point a,point b)
   7 {return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
   8 void swap(point &a,point &b)
   9 {point tt;tt=a,a=b,b=tt;}
  10 bool cmp(const point &a,const point &b)
  11 {
  12     if(fabs(det(p[0],a,b))<eps)
  13         return dis(p[0],a)<dis(p[0],b);
  14     return det(p[0],a,b)>0;
  15 }
  16
  17
  18 void Convex_Hull(point *p,long n,point *stack,long& top)
  19 {
  20     long i;
  21     for(i=1;i<n;i++)
  22         if(p[i].y<p[0].y||fabs(p[i].y-p[0].y)<eps&&p[i].x<p[0].x)
  23             swap(p[i],p[0]);
  24     sort(p+1,p+n,cmp);
  25     stack[top++]=p[0];
  26     for(i=1;i<n;i++)
  27     {
  28         while(top>=2&&det(stack[top-2],stack[top-1],p[i])<=0)
  29             top--;
  30         stack[top++]=p[i];
  31     }
  32     sta[top]=p[0];
  33 }