Geometry

Core Concepts

Point — an (x, y) coordinate pair; usually integer or float in LeetCode problems.

Vector — directed segment from A to B: v = (B.x - A.x, B.y - A.y). Encodes direction and magnitude.

Dot product — A · B = A.x*B.x + A.y*B.y; equals |A||B|cos(θ). Zero → perpendicular; same sign as angle between vectors.

Cross product (2D) — A × B = A.x*B.y - A.y*B.x; equals |A||B|sin(θ). Sign encodes orientation:

• Positive → counter-clockwise (left turn)
• Negative → clockwise (right turn)
• Zero → collinear

Orientation — for three points P, Q, R: compute cross(Q−P, R−P). This single primitive underlies nearly all computational geometry algorithms.

Collinearity — three points are collinear when their cross product is 0; equivalently (y2−y1)*(x3−x1) == (y3−y1)*(x2−x1) (avoids division).

Euclidean distance — sqrt(dx² + dy²); use squared distance dx*dx + dy*dy when only comparison is needed, eliminating float sqrt entirely.

Manhattan distance — |x2−x1| + |y2−y1|; natural for grid movement.

Convex polygon — all cross products of consecutive edges share the same sign; no interior reflex angle.

Lattice point — a point with integer coordinates; important for Pick's theorem and slope representation.

---

Types / Variants

---

Key Algorithms

Orientation Test

Determines the turn direction P→Q→R.

def orient(p, q, r):
    return (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])

Returns positive (CCW), negative (CW), or 0 (collinear). O(1). The foundation for convex hull, segment intersection, and point-in-polygon.

Shoelace Formula (Polygon Area)

For ordered vertices (x1,y1), ..., (xn,yn):

2 * Area = |Σ (x_i * y_{i+1} − x_{i+1} * y_i)|   (indices mod n)

O(n). The unabsoluted signed result is positive for CCW ordering — keep the sign when hull orientation matters.

Pick's Theorem

For a lattice polygon: A = I + B/2 − 1, where A = area (via Shoelace), B = boundary lattice points, I = interior lattice points. B for one edge = gcd(|dx|, |dy|). O(n). Lets you recover I or B from the other two quantities.

Convex Hull (Graham Scan)

Finds the smallest convex polygon enclosing all input points.

1. Sort points by x, breaking ties by y.
2. Build lower hull, then upper hull; for each point pop the stack while orient(stack[-2], stack[-1], p) ≤ 0.

O(n log n). Use < 0 instead of ≤ 0 to exclude collinear boundary points from the hull.

Convex Hull (Jarvis March)

Iteratively picks the point with smallest polar angle from the current hull edge. O(nh) where h = hull size. Prefer over Graham when h ≪ n (e.g., near-circular input).

Segment Intersection

Two segments AB and CD properly intersect iff:

• orient(A,B,C) and orient(A,B,D) have opposite signs, AND
• orient(C,D,A) and orient(C,D,B) have opposite signs.

Collinear overlap (T-intersections, endpoints) needs a separate on-segment bounding-box check. O(1) per pair.

Point in Polygon (Ray Casting)

Cast a horizontal ray rightward from the query point; count edge crossings. Odd = inside. Works for any simple polygon. O(n). Standard fix for vertex ambiguity: treat edges as half-open (y1 ≤ py < y2).

For convex polygons: binary search on polar angle from a known interior point → O(log n).

Closest Pair of Points

Divide by median x; recurse on each half; merge by scanning only the strip of width 2d around the median. At most 8 candidates per point in the strip. O(n log n). Brute force O(n²) is fine for n ≤ 1000.

Segment Intersection Point

Parametrize: P + t*(Q−P) = R + s*(S−R). Solve for t using cross products; parallel lines have zero denominator. O(1). Introduce floats here — only when the actual intersection coordinate is needed, not just existence.

Distance: Point to Line

For line through A, B: dist = |cross(B−A, P−A)| / |B−A|. Use squared numerator/denominator when only comparison is needed. O(1).

---

Advanced Techniques

Rotating Calipers

Solves polygon diameter, minimum width, and minimum bounding rectangle in O(n) after hull construction.

Mechanism: Maintain two antipodal pointer indices; advance the one whose hull edge subtends a smaller angle, decided by cross product. No backtracking.

When to use over brute force: n > ~1000 hull vertices, or the problem explicitly asks for farthest pair, minimum width, or best-fit rectangle on a convex shape. For small n or non-convex shapes, O(n²) brute force is simpler and sufficient.

Sweep Line

Processes events (segment endpoints, point x-coords) sorted by x; maintains an active structure ordered by y at the current sweep position.

Mechanism: Event queue (sorted array or heap); for each event update and query the active set (BST or sorted list).

When to use: Segment intersection counting, rectangle union area, closest-pair strip merge. Use over point-by-point brute force when n > 10⁴ and a spatial ordering is needed. O(n log n).

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Float equality: Comparing floats with == for collinearity or intersection is unreliable. Use integer cross products on integer inputs; use an epsilon for float inputs — never mix strategies.
• Slope as float: dy/dx causes division-by-zero on vertical lines and precision loss. Always reduce to (dy//gcd, dx//gcd) with consistent sign normalisation.
• Collinear hull points: Graham scan with ≤ 0 pop includes collinear points on the hull boundary; < 0 excludes them. The correct choice depends on whether the problem counts collinear boundary points. Be explicit before coding.
• Duplicate points: Max-points-on-line must count duplicates separately (accumulate a per-anchor duplicate counter). Convex hull algorithms typically require deduplication first.
• Degenerate polygon: A polygon with all collinear vertices has zero Shoelace area. Don't infer convexity from area sign alone.
• Signed area: abs() on the Shoelace result discards winding order. Retain the sign when hull orientation or polygon winding direction is needed.
• Collinear segment intersection: The orientation test alone handles the general case but misses T-intersections and endpoint overlaps. Add a bounding-box check min(x1,x2) ≤ px ≤ max(x1,x2) for the collinear branch.
• Integer overflow: Coordinates up to 10⁴ → cross products up to 10⁸ (fine for 32-bit). Coordinates up to 10⁹ → cross products up to 10¹⁸ (needs 64-bit or Python int).
• Ray casting vertex ambiguity: A ray passing exactly through a vertex is counted twice without a convention. Use half-open edges: count crossing only if min(y1,y2) ≤ py < max(y1,y2).
• Graham scan with 1 or 2 points: Standard implementation may return an empty or one-point hull. Guard explicitly before indexing stack[-2].

---

Implementation Notes

• Python math.gcd is always non-negative; normalise sign manually for slope fractions: if dx < 0 negate both; if dx == 0 and dy < 0 negate dy.
• sorted with a cross-product comparator requires functools.cmp_to_key; a direct lambda returning negative/zero/positive won't work as a sort key.
• Prefer cross product angle comparisons over math.atan2 — faster and free of float error.
• Python integers are unbounded; no overflow concern. In C++, use long long for coordinates ≥ 10⁵.
• Segment intersection returning a coordinate (not just bool) requires floats; keep integer-only checks separate from coordinate-finding code.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Collinearity / Line

• Max Points on a Line (hard) — slope grouping with reduced (dy, dx) fractions

Area / Polygon

• Rectangle Area (medium) — axis-aligned rectangle union area
• Minimum Area Rectangle (medium) — hash-based diagonal point lookup
• Minimum Area Rectangle II (medium) — vector rotation and dot/cross product checks

Convex Hull

• Erect the Fence (hard) — convex hull retaining collinear boundary points

Distance

• K Closest Points to Origin (medium) — squared Euclidean + heap or quickselect
• Minimum Time Visiting All Points (easy) — Chebyshev distance

Segment / Intersection

• Line Reflection (medium) — axis-aligned symmetry check
• Check if Two Line Segments Intersect — orientation test with collinear case

Simulation / Direction

• Robot Bounded in Circle (medium) — direction vector after 4-cycle simulation

Clarification Questions to Ask

• Are coordinates integers or floats? (Determines whether integer arithmetic is safe throughout.)
• Can duplicate points appear? (Affects collinearity counting and hull algorithms.)
• Is polygon input guaranteed simple (non-self-intersecting)?
• Are boundary points considered inside or outside for containment queries?
• What output precision is required for area or distance results?

Common Interview Mistakes

• Using float division for slopes when integer cross products suffice — introduces avoidable precision errors.
• Forgetting vertical line handling in slope-based grouping.
• Choosing the wrong ≤ 0 vs < 0 Graham scan pop condition without considering whether collinear boundary points should be included.
• Not deduplicating input before running convex hull.
• Using only the orientation test for segment intersection and missing the collinear-overlap case.
• Using math.sqrt inside distance comparisons instead of squared distance.

Typical Follow-Up Escalations

• "Now return the actual intersection point, not just whether they intersect" → parametric line equations; introduce floats carefully.
• "What if coordinates are up to 10⁹?" → verify cross product fits 64-bit; use Python or long long in C++.
• "Can you handle n = 10⁶ points?" → O(n log n) Graham scan; O(n log n) closest pair divide-and-conquer.
• "Find the farthest pair after building the hull" → rotating calipers on the hull in O(n).
• "Now count interior lattice points" → Pick's theorem from Shoelace area and GCD boundary count.