Merevoli

Convex hull (Graham)

Dec 4th, 2021
638
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Point O;
  2. int n;
  3. Point a[maxn];
  4. void operator -= (Point & a, Point b) {
  5.     a.X -= b.X;
  6.     a.Y -= b.Y;
  7. }
  8. bool ccw(Point o, Point a, Point b) {
  9.     a -= o;
  10.     b -= o;
  11.     return a.X * b.Y > a.Y * b.X;
  12. }
  13. bool cmp(Point a, Point b) {
  14.     return ccw(O, a, b);
  15. }
  16. void graham() {
  17.     sort(a + 1, a + n + 1);
  18.     O = a[1];
  19.     sort(a + 2, a + n + 1, cmp);
  20.     a[0] = a[n];
  21.     a[n + 1] = a[1];
  22.     int j = 1;
  23.     for (int i = 1; i <= n + 1; i++) {
  24.         while (j > 2 && !ccw(a[j - 2], a[j - 1], a[i])) j--;
  25.         a[j++] = a[i];
  26.     }
  27.     n = j - 2;
  28. }
RAW Paste Data