# QuickHull C++ solution 29ms

• 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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.