Geometry

record Point(long x, long y) {}

public long cross(Point o, Point a, Point b) {
    return (a.x - o.x) * (b.y - o.y)
         - (a.y - o.y) * (b.x - o.x);
}

public boolean onSegment(Point p, Point a, Point b) {
    return cross(a, b, p) == 0
        && Math.min(a.x, b.x) <= p.x && p.x <= Math.max(a.x, b.x)
        && Math.min(a.y, b.y) <= p.y && p.y <= Math.max(a.y, b.y);
}

def cross(o, a, b):
    return ((a[0] - o[0]) * (b[1] - o[1])
            - (a[1] - o[1]) * (b[0] - o[0]))

def on_segment(p, a, b):
    return (cross(a, b, p) == 0
            and min(a[0], b[0]) <= p[0] <= max(a[0], b[0])
            and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))

struct Point { long long x, y; };

long long cross(Point o, Point a, Point b) {
    return (a.x - o.x) * (b.y - o.y)
         - (a.y - o.y) * (b.x - o.x);
}

bool onSegment(Point p, Point a, Point b) {
    return cross(a, b, p) == 0
        && min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x)
        && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

function cross(o, a, b) {
  return (
    (a[0] - o[0]) * (b[1] - o[1]) -
    (a[1] - o[1]) * (b[0] - o[0])
  );
}

function onSegment(p, a, b) {
  return (
    cross(a, b, p) === 0 &&
    Math.min(a[0], b[0]) <= p[0] && p[0] <= Math.max(a[0], b[0]) &&
    Math.min(a[1], b[1]) <= p[1] && p[1] <= Math.max(a[1], b[1])
  );
}

public List<Point> hull(List<Point> pts) {
    List<Point> p = new ArrayList<>(pts);
    p.sort(Comparator.comparingLong((Point q) -> q.x)
                   .thenComparingLong(q -> q.y));
    int n = p.size();
    if (n < 3) return p;

    List<Point> h = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        while (h.size() >= 2
               && cross(h.get(h.size() - 2), h.get(h.size() - 1), p.get(i)) <= 0)
            h.remove(h.size() - 1);
        h.add(p.get(i));
    }
    // repeat reversed for upper hull, concatenate, drop duplicate endpoints
    return h;
}

def hull(pts):
    pts = sorted(set(pts))
    if len(pts) < 3:
        return pts

    def half(points):
        h = []
        for q in points:
            while len(h) >= 2 and cross(h[-2], h[-1], q) <= 0:
                h.pop()
            h.append(q)
        return h

    return half(pts)[:-1] + half(pts[::-1])[:-1]

vector<Point> hull(vector<Point> p) {
    sort(p.begin(), p.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    int n = p.size();
    if (n < 3) return p;

    vector<Point> h;
    for (int i = 0; i < n; i++) {
        while (h.size() >= 2
               && cross(h[h.size()-2], h[h.size()-1], p[i]) <= 0)
            h.pop_back();
        h.push_back(p[i]);
    }
    // repeat reversed for upper hull, concatenate
    return h;
}

function hull(points) {
  const pts = [...new Set(points.map(String))]
    .map((s) => s.split(",").map(Number))
    .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  if (pts.length < 3) return pts;

  const half = (list) => {
    const h = [];
    for (const q of list) {
      while (h.length >= 2 && cross(h.at(-2), h.at(-1), q) <= 0)
        h.pop();
      h.push(q);
    }
    return h;
  };

  return [...half(pts).slice(0, -1), ...half([...pts].reverse()).slice(0, -1)];
}

public long distSq(Point a, Point b) {
    long dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

def dist_sq(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

long long distSq(Point a, Point b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

function distSq(a, b) {
  const dx = a[0] - b[0];
  const dy = a[1] - b[1];
  return dx * dx + dy * dy;
}