Orientation and Cross Product
The core integer-geometry predicate behind turns, area tests, segment intersection, and hull construction.
Orientation and Cross Product
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Most contest geometry starts with one predicate: given three points, do they make a left turn, a right turn, or stay collinear? That question is answered by the cross product, and once that primitive is solid, many other routines become simple compositions of it.
When to Use It
Use orientation and cross products when:
you need to compare turns without floating-point angles,
the task asks about segment intersection, convexity, polygon area, or hull building,
integer coordinates are available and exact predicates matter.
Core Idea
For vectors \(\vec{u} = (x_1, y_1)\) and \(\vec{v} = (x_2, y_2)\), the 2D cross product is \[ \vec{u} \times \vec{v} = x_1 y_2 - y_1 x_2. \]
For three points \(a, b, c\), compute \[ (b - a) \times (c - a). \] Its sign tells the turn:
positive: left turn,
negative: right turn,
zero: collinear.
Key Insight
The cross product is both a turn test and a signed-area test. Its magnitude is twice the signed area of triangle \(abc\). That one fact explains why it appears in hulls, polygon area, intersection predicates, and half-plane tests.
Operations / Main Technique
orientation: left / right / collinear.
on-segment test: after confirming collinearity, check whether a point lies inside the bounding box.
polygon area: sum edge cross products.
turn filtering: keep only left turns when building a convex hull.
Worked example.
If \(a = (0,0)\), \(b = (3,0)\), and \(c = (1,2)\), then \[ (b-a) \times (c-a) = 3 \cdot 2 - 0 \cdot 1 = 6 > 0, \] so \(a \to b \to c\) is a left turn.
Correctness Intuition
The sign of the cross product tells which side of the directed line \(a \to b\) the point \(c\) lies on. Everything else is built on top of that side test. Since the computation uses only integer arithmetic, the predicate is exact as long as overflow is avoided.
Complexity Analysis
Each primitive here is \(O(1)\) time and \(O(1)\) memory.
Implementation
The reference code provides:
a point type on 64-bit integers,
cross(a, b, c)for orientation,orientreturning \(-1, 0, 1\),on_segmentfor boundary checks.
Common Pitfalls
Using
intwhen coordinates can make the cross product overflow.Forgetting that a zero cross product only means collinear, not necessarily on the segment.
Mixing clockwise and counterclockwise conventions between notes and code.
Reaching for \(\texttt{atan2}\) when a sign test would be simpler and more reliable.
Variants / Extensions
Dot product for projection and angle-related tests.
Shoelace formula for polygon area.
Orientation as the core primitive for segment intersection and convex hull.
Practice Problems
Determine whether two segments intersect.
Compute polygon area from its vertices.
Filter turns while constructing a convex hull.
Check whether a polygon is strictly convex.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Point {
long long x;
long long y;
};
Point operator-(Point a, Point b) {
return {a.x - b.x, a.y - b.y};
}
long long cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
long long cross(Point a, Point b, Point c) {
return cross(b - a, c - a);
}
int orient(Point a, Point b, Point c) {
long long value = cross(a, b, c);
if (value > 0) return 1;
if (value < 0) return -1;
return 0;
}
bool on_segment(Point a, Point b, Point p) {
if (orient(a, b, p) != 0) return false;
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.