# Convex Hull

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

// Usage:
//      ConvexHull hull;
//      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;
}

};
```