# A very concise c++ Graham Algorithm with explaination

• A very concise c++ Graham Algorithm. Reference https://segmentfault.com/a/1190000000488339 if you can read Chinese :)
steps:

1. sort the points by x, y
2. start from the first point on the left lower corner and scan the lower chain of the convex hull
3. start from the last point on the right upper corner and scan the upper chain of the convex hull
`````` //Graham Algorithm
//ref https://segmentfault.com/a/1190000000488339
bool PointLess(const Point &a, const Point &b)
{
if (a.x == b.x)
return a.y < b.y;

return a.x < b.x;
}

class Solution {
public:
vector<Point> outerTrees(vector<Point>& points) {
int len = points.size();
if (len < 4)
return points;
//sort the points by x as first key, y as second key
vector<Point> convexHull;
sort(points.begin(), points.end(), PointLess);

//find the lower chain
for (int i = 0; i < len; ++i)
{

while (convexHull.size()  > 1)
{
int n = convexHull.size();
Point vec1(convexHull[n-1].x - convexHull[n-2].x, convexHull[n-1].y - convexHull[n-2].y);
Point vec2(points[i].x - convexHull[n-1].x, points[i].y - convexHull[n-1].y);
//the cross product is negative, a concave inner angle is found, should pop the last point
if ((vec1.x*vec2.y - vec2.x*vec1.y) < 0)
convexHull.pop_back();
else
break;
}
convexHull.push_back(points[i]);
}

// find the upper chain
int lower = convexHull.size();
for (int i = len - 2; i >= 0; --i)
{
while (convexHull.size()  > lower)
{
int n = convexHull.size();

Point vec1(convexHull[n - 1].x - convexHull[n - 2].x, convexHull[n - 1].y - convexHull[n - 2].y);
Point vec2(points[i].x - convexHull[n - 1].x, points[i].y - convexHull[n - 1].y);

//the cross product is negative, a concave inner angle is found, should pop the last point
if ((vec1.x*vec2.y - vec2.x*vec1.y) < 0)
convexHull.pop_back();
else
break;
}
convexHull.push_back(points[i]);

}
//pop the last one because it is same as first one
convexHull.pop_back();

return convexHull;
}
``````

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