lib/Documentation/docs-sonyckson/myg.cpp

   1 // Implementation of Monotone Chain Convex Hull algorithm.
   2 #include <algorithm>
   3 #include <cstdlib>
   4 #include <cstdio>
   5 #include <iostream>
   6 #include <sstream>
   7 #include <vector>
   8 using namespace std;
   9 #define ll long long
  10 struct point {
  11         int x, y;
  12         point(){}
  13         point(int a, int b){ x = a;y = b;}
  14         bool operator <(const point &p) const {
  15                 return x < p.x || (x == p.x && y < p.y);
  16         }
  17 };
  18
  19 // 2D cross product.
  20 // Return a positive value, if OAB makes a counter-clockwise turn,
  21 // negative for clockwise turn, and zero if the points are collinear.
  22 int cross(const point &O, const point &A, const point &B)
  23 {
  24         return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  25 }
  26
  27 // Returns a list of points on the convex hull in counter-clockwise order.
  28 // Note: the last point in the returned list is the same as the first one.
  29 vector<point> convexHull(vector<point> P)
  30 {
  31         int n = P.size(), k = 0;
  32         vector<point> H(2*n);
  33         // Sort points lexicographically
  34         sort(P.begin(), P.end());
  35         // Build lower hull
  36         for (int i = 0; i < n; i++) {
  37                 while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  38                 H[k++] = P[i];
  39         }
  40         // Build upper hull
  41         for (int i = n-2, t = k+1; i >= 0; i--) {
  42                 while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  43                 H[k++] = P[i];
  44         }
  45         H.resize(k);
  46         return H;
  47 }
  48 /////////////////////////      hiiiiper rapida :)
  49 int TAM;
  50 point H[1500];
  51 void convexHull(point P[], int n)
  52 {
  53         int k = 0;
  54         // Sort points lexicographically
  55         sort(P, P+n);
  56         // Build lower hull
  57         for (int i = 0; i < n; i++) {
  58                 while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  59                 H[k++] = P[i];
  60         }
  61         // Build upper hull
  62         for (int i = n-2, t = k+1; i >= 0; i--) {
  63                 while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  64                 H[k++] = P[i];
  65         }
  66         TAM = k;
  67 }