Pseudo code (from Wikipedia):

Input = a set S of n points

Assume that there are at least 2 points in the input set S of points

QuickHull (S)

{

// Find convex hull from the set S of n points

Convex Hull := {}

Find left and right most points, say A & B, and add A & B to convex hull

Segment AB divides the remaining (n-2) points into 2 groups S1 and S2

where S1 are points in S that are on the right side of the oriented line from A to B,

and S2 are points in S that are on the right side of the oriented line from B to A

FindHull (S1, A, B)

FindHull (S2, B, A)

}

FindHull (Sk, P, Q)

{

// Find points on convex hull from the set Sk of points

// that are on the right side of the oriented line from P to Q

If Sk has no point, then return.

From the given set of points in Sk, find farthest point, say C, from segment PQ

Add point C to convex hull at the location between P and Q

Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2

where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented

line from P to C, and S2 are points on the right side of the oriented line from C to Q.

FindHull(S1, P, C)

FindHull(S2, C, Q)

}

Output = convex hull

```
class Solution {
public:
static bool mycmp(Point &a, Point &b) {
return a.x < b.x;
}
int testSide(Point &a, Point &b, Point &c) {
// cross product of (AB and AC vectors)
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
double distPointLine(Point &A, Point &B, Point &C) {
// dist(line: ax+by+c=0, and point(x0, y0)): (a*x0 + b*y0 + c)/sqrt(a^2+b^2)
// line: (y2-y1)*x - (x2-x1)*y + x2*y1 - y2*x1 = 0
int a = B.y - A.y, b = B.x - A.x;
return abs((a*C.x - b*C.y + B.x*A.y - B.y*A.x)/sqrt(a*a + b*b));
}
void FindHull(vector<Point> &points, Point &A, Point &B) {
if (points.empty())
return;
int idx = 0;
double dist = distPointLine(A, B, points[0]);
for (int i=1; i<points.size(); i++) {
if (distPointLine(A, B, points[i]) > dist) {
dist = distPointLine(A, B, points[i]);
idx = i;
}
}
ret.push_back(points[idx]);
vector<Point> R, T;
for (int i=0; i<points.size(); i++) {
if (i != idx) {
int tmp = testSide(A, points[idx], points[i]);
if (tmp >= 0)
R.push_back(points[i]);
else {
tmp = testSide(points[idx], B, points[i]);
if (tmp >= 0)
T.push_back(points[i]);
}
}
}
FindHull(R, A, points[idx]);
FindHull(T, points[idx], B);
return;
}
vector<Point> ret;
vector<Point> outerTrees(vector<Point>& points) {
// find the convex hull; use QuickHull algorithm
if (points.size() <= 1)
return points;
// find the left most and right most two points
sort(points.begin(), points.end(), mycmp);
ret.push_back(points[0]);
ret.push_back(points.back());
// test whether a point on the left side right side or on the line
vector<Point> Left, Right, Online;
for (int i=1; i<points.size()-1; i++) {
int tmp = testSide(points[0], points.back(), points[i]);
if (tmp < 0)
Right.push_back(points[i]);
else if (tmp > 0)
Left.push_back(points[i]);
else
Online.push_back(points[i]);
}
// if Upper or Down is empty, Online should be pushed into ret
if (Left.empty() || Right.empty())
for (int i=0; i<Online.size(); i++)
ret.push_back(Online[i]);
FindHull(Left, points[0], points.back());
FindHull(Right, points.back(), points[0]);
return ret;
}
};
```