uva 681 - Convex Hull Finding

  1  /*
  2  Problem link
  3  Type: Geometry
  4  Algorithm: Graham's Scan
  5      Choose a pivot points, in this problem I choose
  6      the most bottom - most left point.
  7  
  8      Sort the points according to the corner made with
  9      the pivot point.
 10  
 11      Create a stack S (vector), push the point P[n-1],
 12      P[0], P[1]. For each point i (i>=2), if S[top-1],
 13      S[top], P[i] turn left then push P[i] in the stack,
 14      otherwise Pop the top of S.
 15  
 16      The remaining of S after the process is the convex hull,
 17      this algorithm run in O(nlogn) for the sorting and O(n)
 18      for the Graham's Scan ---> Complexity O(nlogn)
 19  */
 20  #include <iostream>
 21  #include <cstdio>
 22  #include <cstring>
 23  #include <cmath>
 24  #include <cstdlib>
 25  #include <vector>
 26  #include <stack>
 27  #include <algorithm>
 28  using namespace std;
 29  const double EPS = 1E-9;
 30  int maxn = 10000;
 31  
 32  /* Implementation for Geometry library */
 33  class Point {
 34  public:
 35      double x, y;
 36  public:
 37      Point() { x = 0.0; y = 0.0;}
 38      Point(double _x, double _y): x(_x), y(_y) {};
 39      Point(const Point &aPoint) {
 40          this->x = aPoint.x;
 41          this->y = aPoint.y;
 42      }
 43  
 44      bool operator == (Point &aPoint) const {
 45          return (fabs(this->x-aPoint.x)<EPS && fabs(this->y-aPoint.y)<EPS);
 46      }
 47  };
 48  
 49  // Distance between 2 points
 50  double dist(Point a, Point b) {
 51      return (hypot(a.x - b.x, a.y - b.y));
 52  }
 53  
 54  class Vec {
 55  public:
 56      double x, y;
 57  public:
 58      Vec(double _x, double _y): x(_x), y(_y) {}
 59  };
 60  
 61  // Return a vector from 2 points
 62  Vec toVec(Point a, Point b) {
 63      return Vec(b.x - a.x, b.y - a.y);
 64  }
 65  
 66  // Calculate cross product of 2 vectors
 67  double cross(Vec a, Vec b) { return (a.x*b.y - b.x*a.y); }
 68  
 69  // Check if the path from point p->q->r is a left turn
 70  bool ccw(Point p, Point q, Point r) {
 71      return (cross(toVec(p,q), toVec(p,r)) > 0);
 72  }
 73  
 74  // Check if 3 points are collinear
 75  bool collinear(Point p, Point q, Point r) {
 76      return (fabs(cross(toVec(p,q), toVec(p,r))) < EPS);
 77  }
 78  
 79  // Compare angle x'(Pivot)a and x'(Pivot)b with (Pivot)x' // Ox
 80  bool angleCmp(Point a, Point b, Point pivot) {
 81      if (collinear(pivot, a, b)) {
 82          return dist(pivot, a) < dist(pivot, b);
 83      }
 84      double d1x = a.x - pivot.x, d1y = a.y - pivot.y;
 85      double d2x = b.x - pivot.x, d2y = b.y - pivot.y;
 86      return (atan2(d1y, d1x) - atan2(d2y, d2x) < 0);
 87  }
 88  
 89  Point pivot;
 90  bool cmp(const Point &a, const Point &b) {
 91      return angleCmp(a, b, pivot);
 92  }
 93  
 94  // Get the convex hull of the set of point P using Graham's Scan algorithm
 95  class Polygon {
 96  private:
 97      vector<Point> P;
 98      int n;
 99  public:
100      Polygon(vector<Point> _P): P(_P) {
101          n = (int)P.size();
102          int P0 = 0;
103          for (int i = 1; i < n; i++)
104              if (P[i].y < P[P0].y || (fabs(P[i].y-P[P0].y)<EPS && P[i].x < P[P0].x)) P0 = i;
105          Point tmp = P[0]; P[0] = P[P0]; P[P0] = tmp;
106          pivot = P[0];
107          std::sort(++P.begin(), P.end(), cmp);
108      }
109  
110      vector<Point> getConvexHull() {
111          if (n<=3) {
112              if (!(P[0] == P[n-1])) P.push_back(P[0]);
113              return P;
114          }
115  
116          vector<Point> S;
117          S.push_back(P[n-1]); S.push_back(P[0]); S.push_back(P[1]);
118  
119          int i = 2;
120          while (i < n) {
121              int j = (int)S.size()-1;
122              if (ccw(S[j-1],S[j],P[i])) S.push_back(P[i++]);
123              else S.pop_back();
124          }
125          S.erase(S.begin());
126          S.push_back(Point(*S.begin()));
127          return S;
128      }
129      ~Polygon() { P.clear(); }
130  };
131  /* End implementation for Geometry library */
132  
133  int n;
134  vector<Point> P;
135  
136  void readFile();
137  
138  int main()
139  {
140      int nTest;
141      cin >> nTest;
142      cout << nTest << endl;
143      while (nTest--) {
144          P.clear();
145          readFile();
146          Polygon myPolygon(P);
147          vector<Point> result = myPolygon.getConvexHull();
148          cout << (int)result.size() << endl;
149          for (int i = 0; i < (int)result.size(); i++)
150              cout << (int)result[i].x << " " << (int)result[i].y << endl;
151          if (nTest != 0) cout << -1 << endl;
152      }
153      return 0;
154  }
155  
156  void readFile() {
157      cin >> n;
158      for (int i = 1; i < n; i++) {
159          int x, y;
160          cin >> x >> y;
161          P.push_back(Point(x,y));
162      }
163      cin >> n; // Trash
164      cin >> n; // Trash
165      cin >> n; // Trash
166  }