Algorithm
// Sort by (x, y)
List lower = new ArrayList<>();
for (Point p : points) {
while (lower.size() >= 2 && cross(lower.get(lower.size()-2), lower.get(lower.size()-1), p) <= 0)
lower.remove(lower.size()-1);
lower.add(p);
}
// Similarly build upper (iterate reverse)
// Combine: lower[0..last-1] + upper[0..last-1] Advertisement
Complexity
O(N log N). Cleaner code than Graham. No angle sort — just coordinate sort.
Advertisement
Handling collinear
Change ≤ 0 to < 0 in cross check to keep collinear points on hull. Or stay strict to keep vertices only.
Integer safe
Cross product uses only integers → exact. No trig, no floats.