볼록 껍질 (Convex Hull)

# Andrew's monotone chain O(N log N)
def ccw(ax, ay, bx, by, cx, cy):
  return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
​
def convex_hull(points):
  points = sorted(set(points))    # 중복 제거 + 정렬
  if len(points) <= 1: return points
  lower = []
  for p in points:
      while len(lower) >= 2 and ccw(*lower[-2], *lower[-1], *p) <= 0:
          lower.pop()
      lower.append(p)
  upper = []
  for p in reversed(points):
      while len(upper) >= 2 and ccw(*upper[-2], *upper[-1], *p) <= 0:
          upper.pop()
      upper.append(p)
  return lower[:-1] + upper[:-1]
​
pts = [(0,0), (1,1), (2,0), (1,-1), (0,1)]
hull = convex_hull(pts)
print("Convex Hull:")
for x, y in hull:
  print(f"({x}, {y})")

// Andrew's monotone chain O(N log N)
import java.util.*;
​
public class Main {
  static class Point implements Comparable<Point> {
      long x, y;
      Point(long x, long y) { this.x = x; this.y = y; }
      public int compareTo(Point o) {
          return x != o.x ? Long.compare(x, o.x) : Long.compare(y, o.y);
      }
  }
  static long ccw(Point a, Point b, Point c) {
      return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  }
  static List<Point> convexHull(List<Point> pts) {
      int n = pts.size();
      if (n <= 1) return pts;
      Collections.sort(pts);
      List<Point> hull = new ArrayList<>();
      // lower
      for (int i = 0; i < n; i++) {
          while (hull.size() >= 2 && ccw(hull.get(hull.size()-2),
                 hull.get(hull.size()-1), pts.get(i)) <= 0) hull.remove(hull.size()-1);
          hull.add(pts.get(i));
      }
      int lowerSz = hull.size();
      // upper
      for (int i = n - 2; i >= 0; i--) {
          while (hull.size() > lowerSz && ccw(hull.get(hull.size()-2),
                 hull.get(hull.size()-1), pts.get(i)) <= 0) hull.remove(hull.size()-1);
          hull.add(pts.get(i));
      }
      hull.remove(hull.size()-1);  // 시작점 중복 제거
      return hull;
  }
  public static void main(String[] args) {
      List<Point> pts = Arrays.asList(
          new Point(0,0), new Point(1,1), new Point(2,0),
          new Point(1,-1), new Point(0,1));
      List<Point> hull = convexHull(pts);
      System.out.println("Convex Hull:");
      for (Point p : hull) System.out.println("(" + p.x + ", " + p.y + ")");
  }
}