CONCEPT · Legendary
Computational geometry
also cross product · orientation · convex hull
The 2-D cross product is the signed turn. Hulls, intersections, and point-in-polygon all start there. Prefer integer math over atan2.
Intuition
Left, right, or on the line — one determinant. Everything else is that test in a loop.
When to reach for it
- CSES Point Location, Segment Intersection, Convex Hull
- Collinearity, polygon area (shoelace)
- Convex polygon queries in log n
Usual pits
- int overflow on 1e9 × 1e9
- Float epsilon instead of integer cross
- O(n) point-in-polygon at n,q=1e5 on a concave polygon
- Hull collinear policy vs the statement