📜 WAYPOINT LESSON
Orientation and Convex Hulls
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 177 of 281
Everything starts with the cross product's sign; the monotone chain builds the hull in O(n log n) with pure integer arithmetic.
The sign of a cross product
cross(O, A, B) > 0: counter-clockwise turn; < 0: clockwise; = 0: collinear. The monotone chain sorts points, walks the lower then upper boundary popping non-left turns, and never divides — no precision bugs. Shoelace over the hull gives the doubled area: keep it doubled, it is always an integer.