[Template] Convex Hull

struct Point {  
      int x, y;  
      Point(int x = 0, int y = 0)  
            : x(x), y(y) {}  
};  
  
bool cmp(Point a, Point b) {  
      return a.x < b.x || (a.x == b.x && a.y < b.y);  
}  
  
bool cw(Point a, Point b, Point c) {  
      return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;  
}  
  
bool ccw(Point a, Point b, Point c) {  
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;  
}  
  
vector <Point> convex_hull(vector <Point>& a) {  
      if (a.size() == 1) {  
            return {};  
      }  
      sort(a.begin(), a.end(), &cmp);  
      Point p1 = a[0];  
      Point p2 = a.back();  
      vector <Point> up;  
      vector <Point> down;  
      up.push_back(p1);  
      down.push_back(p1);  
      for (int i = 1; i < (int)a.size(); i++) {  
            if (i == a.size() - 1 || cw(p1, a[i], p2)) {  
                  while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i])) {  
                        up.pop_back();  
                  }  
                  up.push_back(a[i]);  
            }  
            if (i == a.size() - 1 || ccw(p1, a[i], p2)) {  
                  while(down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i])) {  
                        down.pop_back();  
                  }  
                  down.push_back(a[i]);  
            }  
      }  
      vector <Point> hull;  
      for (int i = 0; i < (int)up.size(); i++) {  
            hull.push_back(up[i]);  
      }  
      for (int i = down.size() - 2; i > 0; i--) {  
            hull.push_back(down[i]);  
      }  
      return hull;  
}