// LLP-ConvexHull: eliminate interior points to find convex hull membership.
// px[j], py[j] are x,y coordinates of point j.

class LLPConvexHull {
  void LLPConvexHull(double[] px, double[] py) {
    boolean[] G = true;
    forbidden (j) : G[j] && isInterior(j, px, py, G) =>
      advance : G[j] = false;
  }

  boolean isInterior(int j, double[] px, double[] py, boolean[] G) {
    int i = 0;
    while (i < px.length) {
      if (i != j && G[i]) {
        int k = i + 1;
        while (k < px.length) {
          if (k != j && G[k]) {
            int l = k + 1;
            while (l < px.length) {
              if (l != j && G[l]) {
                if (insideTriangle(px, py, j, i, k, l)) {
                  return true;
                }
              };
              l = l + 1;
            }
          };
          k = k + 1;
        }
      };
      i = i + 1;
    };
    return false;
  }

  boolean insideTriangle(double[] px, double[] py, int j, int a, int b, int c) {
    double d1 = sign(px[j], py[j], px[a], py[a], px[b], py[b]);
    double d2 = sign(px[j], py[j], px[b], py[b], px[c], py[c]);
    double d3 = sign(px[j], py[j], px[c], py[c], px[a], py[a]);
    boolean hasNeg = (d1 < 0.0) || (d2 < 0.0) || (d3 < 0.0);
    boolean hasPos = (d1 > 0.0) || (d2 > 0.0) || (d3 > 0.0);
    return !hasNeg || !hasPos;
  }

  double sign(double x1, double y1, double x2, double y2, double x3, double y3) {
    return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
  }
}