Geometry: orientation before distance
Picture
From A to B to C, a cross product is positive for a left turn, negative for right, and zero for collinear.
Predict
What does a zero cross product mean?
Walk through the small example
The three points are collinear. Cross-product sign supplies an exact turn test; sorted order lets a stack maintain a convex boundary.
Mental model and complete Python solution
Walk sorted points while pulling a taut string around them. If the newest bend turns inward, the middle point cannot remain on the outer boundary, so pop it.
What the function promises: Return convex-hull vertices counterclockwise without repeating the first point. Integer input is used; collinear interior points are omitted.
def orientation(a, b, c):
return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
def convex_hull(points):
points = sorted(set(points))
if len(points) <= 1: return points
def chain(sequence):
result = []
for point in sequence:
while len(result) >= 2 and orientation(result[-2], result[-1], point) <= 0:
result.pop()
result.append(point)
return result
lower = chain(points)
upper = chain(reversed(points))
return lower[:-1] + upper[:-1]
assert convex_hull([(0,0),(1,0),(1,1),(0,1),(0,0),(0,0)]) == [(0,0),(1,0),(1,1),(0,1)]
assert convex_hull([(0,0),(1,0),(2,0)]) == [(0,0),(2,0)]Work and storage: O(n log n) time for sorting and O(n) stack/output space.
When to recognize it: Cross-product sign supplies an exact turn test; sorted order lets a stack maintain a convex boundary.
Check before applying it: Floating-point coordinates need robust predicates, and the collinear-boundary policy must be explicit.
Change one rule
Keep every boundary-collinear point.
See what changes
Change the pop inequality and deduplicate carefully so collinear edge points remain once.
Connect
invariants: The stack remains a convex chain after every point.
Sorting: buy useful order: Lexicographic order makes the boundary build monotone.