convex hull

1. Find a point C that is inside the convex hull of S ( (sum of x coordinates)/ n, (sum of y coordinates)/n )
2. Sort S by polar angle and within polar angle by distance from C. Use atan2(y-Cy , x-Cx) c++ function.
3. Create a doubly linked circular list of points using above order Let right link to the next point in the order and left link to the previous point

   
   

4. Let p be the point that the smallest y-coordinate (break a tie, if any, by selecting the one with largest x-coordinate)
5. use Law of cosines to calculate angle formed by x, rx and rrx
    for (x = p; rx = point to the right of x; x != rx) { 
          rrx = point to the right of rx; 
          if (angle formed by x, rx, and rrx is <=180 degrees) { 
              delete rx from the list; 
              rx = x; 
              x = point on left of rx; 
          } 
          else { 
          x = rx; rx = rrx;} 
      }
6. For convex hull problem, you can use double link list to store all the extreme points. Because it need to use three consequence points to measure the degree to judge if it’s less than 180 degrees. So double link list is the best data structure to use.