// 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;

  }

}