// from https://www.geeksforgeeks.org/convex-hull-using-jarvis-algorithm-or-wrapping/

sclass ConvexHull2D {
  settable IDoublePt[] points;
  gettable L<IDoublePt> hull;
  
  *() {}
  *(Cl<IDoublePt> points) {
    this.points = toTypedArray(IDoublePt, points);
  }
  
  // To find orientation of ordered triplet (p, q, r).
  // The function returns following values
  // 0 --> p, q and r are collinear
  // 1 --> Clockwise
  // 2 --> Counterclockwise
  int orientation(IDoublePt p, IDoublePt q, IDoublePt r)
  {
    double val =
      (q.y_double() - p.y_double()) * (r.x_double() - q.x_double()) -
      (q.x_double() - p.x_double()) * (r.y_double() - q.y_double());
   
    if (val == 0) ret 0;  // collinear
    ret val > 0 ? 1 : 2; // clock or counterclock wise
  }
    
  run {
    if (hull != null) ret;
    int n = l(points);
    hull = new L;

    // Less than 3 points -> hull is all points
    if (n < 3)
      ret with addAll(hull, points);
    
    // Find the leftmost point
    int l = 0;
    for (int i = 1; i < n; i++)
      if (points[i].x_double() < points[l].x_double())
        l = i;
     
    // Start from leftmost point, keep moving 
    // counterclockwise until we reach the start point
    // again. This loop runs O(h) times where h is the
    // number of points in the hull.
    int p = l, q;
    do {
      // Add current point to result
      hull.add(points[p]);
 
      // Search for a point 'q' such that 
      // orientation(p, q, x) is counterclockwise 
      // for all points 'x'. The idea is to keep 
      // track of last visited most counterclock-
      // wise point in q. If any point 'i' is more 
      // counterclock-wise than q, then update q.
      q = (p + 1) % n;
        
      for i to n: {
         // If i is more counterclockwise than 
         // current q, then update q
         if (orientation(points[p], points[i], points[q]) == 2)
            q = i;
      }
 
      // Now q is the most counterclockwise with
      // respect to p. Set p as q for next iteration, 
      // so that q is added to result 'hull'
      p = q;
    } while (p != l);  // While we don't come to first point
  }
  
  L<IDoublePt> get() {
    run();
    ret hull;
  }
}