Convex Hull

#include<bits/stdc++.h>
#define ll long long

// Usage:
//      ConvexHull hull;
//      hull.addPoint(x, y);
//      convexhull = hull.getConvexHull();
struct ConvexHull
{   
    struct Point {
        
        double x, y;
        
        Point(){}
        
        Point(double _1, double _2) : x(_1), y(_2) {}
        
        bool operator < (Point b) const {
            if (x != b.x)
                return x < b.x;
            return y < b.y;
        }
    };
    
    vector<Point> a;
    set<Point> bag;
    
    ConvexHull () {
        a.clear();
        bag.clear();
    }

    void clear() {
        a.clear();
        bag.clear();
    }
    
    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;
    }
    
    void addPoint(double x, double y) {
        bag.insert(Point(x, y));
    }

    vector< pair<double, double> > getConvexHull() {
        
        // take all points from set to vector, sorted by increasing order
        for (auto it = bag.begin(); it != bag.end(); ++it)
            a.push_back(*it);
        
        vector< pair<double, double> > hull;
        
        if (a.size() <= 1) {
            for (auto p : a)
                hull.push_back({p.x, p.y});
            return hull;
        }
                
        Point p1 = a[0], p2 = a.back();
        vector<Point> up, down;
        up.push_back(p1);
        down.push_back(p1);
        
        for (int i = 1; i < 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]);
            }
        }

        for (int i = 0; i < up.size(); i++)
            hull.push_back({up[i].x, up[i].y});
        for (int i = down.size() - 2; i > 0; i--)
            hull.push_back({down[i].x, down[i].y});
        
        return hull;
    }   
        
};