Graham scan idea
Find lowest point (pivot). Sort others by polar angle. Scan + maintain stack of hull vertices.
Advertisement
Cross product for turn direction
int cross(Point o, Point a, Point b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
// >0 = left turn, <0 = right turn, 0 = collinearAdvertisement
Main scan
Point[] sorted = sortByAngle(points, pivot);
Deque hull = new ArrayDeque<>();
for (Point p : sorted) {
while (hull.size() >= 2 && cross(hull.peek().second, hull.peek().first, p) <= 0)
hull.pop();
hull.push(p);
} Complexity
O(N log N) — sort dominates. Scan is O(N) amortized.