Graham Scan Algorithm Implementation

convexhull.cpp

#include <bits/stdc++.h>
using namespace std;

// [Copy Start]
struct Point {
  long long x, y;
};

enum Orientation { CW = -1, COLLINEAR = 0, CCW = 1 };

long long ccw(const Point& a, const Point& b, const Point& c) {
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

Orientation orientation(const Point& a, const Point& b, const Point& c) {
  long long v = ccw(a, b, c);
  if (v > 0) return CCW;
  if (v < 0) return CW;
  return COLLINEAR;
}

vector<Point> convex_hull(vector<Point> pts) {
  sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
  });

  vector<Point> hull;
  for (auto& p : pts) {
    while (hull.size() >= 2 &&
           orientation(hull[hull.size() - 2], hull.back(), p) != CCW)
      hull.pop_back();
    hull.push_back(p);
  }

  int t = hull.size() + 1;
  for (int i = pts.size() - 2; i >= 0; i--) {
    Point p = pts[i];
    while (hull.size() >= t &&
           orientation(hull[hull.size() - 2], hull.back(), p) != CCW)
      hull.pop_back();
    hull.push_back(p);
  }

  hull.pop_back();
  return hull;
}
// [Copy End]

int main() {
  int N;
  cin >> N;
  vector<Point> p(N);
  for (int i = 0; i < N; i++) cin >> p[i].x >> p[i].y;
  vector<Point> hull = convex_hull(p);
  cout << hull.size() << "\n";
  for (int i = 0; i < hull.size(); i++) {
    cout << hull[i].x << " " << hull[i].y << "\n";
  }
  return 0;
}