Merevoli

Convex hull (Monotone chain)

Dec 4th, 2021
546
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Point {
  2.     int X, Y
  3.     bool operator < (const Point & v) {
  4.         return X == v.X ? Y < v.Y : X < v.X;
  5.     }
  6.     int cross(const Point & p,
  7.         const Point & q) const {
  8.         return (p.X - X) * (q.Y - Y) - (p.Y - Y) * (q.X - X);
  9.     }
  10. };
  11. int n;
  12. Point a[maxn], p[maxn];
  13. void monotonechain() {
  14.     sort(a + 1, a + n + 1);
  15.     int k = 1;
  16.     for (int i = 1; i <= n; i++) {
  17.         while (k >= 3 && p[k - 2].cross(p[k - 1], a[i]) <= 0) k--;
  18.         p[k++] = a[i];
  19.     }
  20.     for (int i = n - 1, t = k + 1; i > 0; i--) {
  21.         while (k >= t && p[k - 2].cross(p[k - 1], a[i]) <= 0) k--;
  22.         p[k++] = a[i];
  23.     }
  24.     for (int i = 1; i < k; i++) a[i] = p[i];
  25.     n = k - 2;
  26. }
RAW Paste Data