Lesson 32 · Strings & math

Computational geometry basics

📖 Walk me through it — plain English

Almost every geometry interview question secretly reduces to one tiny calculation called the 2D cross product. Picture standing at point a, facing point b. A third point c is either off to your left, off to your right, or dead ahead on the same straight line. The cross product is a single number whose sign answers exactly that question. The formula is (b.x − a.x)(c.y − a.y) − (b.y − a.y)(c.x − a.x). If it comes out positive, c is a left turn (we call this counter-clockwise); negative means a right turn (clockwise); zero means all three points sit on one line (collinear). The huge win: every input is whole numbers, so this is plain integer multiply-and-subtract — you never divide, never compute a slope, and never hit a floating-point rounding bug.

Analogy: imagine driving and a passenger asks "did we just turn left or right?" You don't need a protractor or exact angles — you only need the direction of the turn. The cross product is that gut-feel answer, distilled to one sign (+, −, or 0).

The main code here uses that turn-test to build a convex hull — the smallest fence that wraps a set of scattered points, like stretching a rubber band around pins on a board and letting it snap tight. Andrew's monotone-chain method first sorts the points left-to-right, then sweeps across building the bottom edge, keeping only points where we keep turning the same way; any point that would create a "dent" (a non-left turn) gets popped off. Let's trace the lower edge on five points: (0,0), (1,1), (2,0), (2,2), (0,2). After sorting by x then y they become (0,0), (0,2), (1,1), (2,0), (2,2). The square's corners should survive; the middle point (1,1) should get thrown away because it sits inside.

Step 1 · Start the bottom chain. Drop in the first two sorted points; with fewer than 3 points there's no turn to test yet. Hull = [(0,0), (0,2)].

0,0

0,2

Step 2 · Next point is (1,1). Test the last two plus it: cross((0,0),(0,2),(1,1)) = (0)(1) − (2)(1) = −2. That's ≤ 0 (not a left turn), so pop (0,2). Then append (1,1). Hull = [(0,0), (1,1)].

0,0

0,2

1,1

Step 3 · Next point is (2,0). Test cross((0,0),(1,1),(2,0)) = (1)(0) − (1)(2) = −2. Again ≤ 0, so pop (1,1) — the inside point is gone. Append (2,0). Hull = [(0,0), (2,0)].

0,0

1,1

2,0

Step 4 · Last point is (2,2). Test cross((0,0),(2,0),(2,2)) = (2)(2) − (0)(2) = +4. Positive — a genuine left turn — so we keep everything and append. Lower chain done = [(0,0), (2,0), (2,2)].

0,0

2,0

2,2

The bottom edge correctly traced the outer corners and tossed the interior point (1,1). The code then runs the exact same sweep on the points in reverse order to build the top edge (upper), and glues the two halves together — dropping the shared endpoints with [:-1] so corners aren't counted twice.

Why it's fast: the sort costs O(n log n), which dominates. The sweep itself is linear — each point is pushed onto the hull once and popped at most once, so even with the inner while loop the total pop work is bounded by n. Overall O(n log n) time, O(n) space. And because the turn-test is pure integer arithmetic, the answer is exact — no slopes, no division, no precision traps.

Most interview geometry reduces to one primitive: the 2D cross product. Given three points, the signed area of the parallelogram they span tells you which way you turn when walking from one to the next. Compute (b - a) × (c - a) = (b.x - a.x)(c.y - a.y) - (b.y - a.y)(c.x - a.x): a positive result means counter-clockwise (left turn), negative means clockwise (right turn), and zero means the three points are collinear. That single sign is the engine behind polygon area (the shoelace formula is just a sum of cross products), segment intersection (do the endpoints of one segment straddle the other?), and convex hull (keep turning the same direction). Because every input is integer in most problems, you can compute this with int math and never touch a floating-point slope — which is exactly how you dodge the precision bugs that sink naive solutions.

Trigger signals

"Points in the plane" / (x, y) coordinates
"Do these two segments cross?"
"Clockwise / counter-clockwise / collinear"
"Area of a polygon"
"Outer boundary / fence / convex hull"
"Max points on one straight line"

Classic problems

Max Points on a Line — slope hashing
Rectangle Overlap — axis-aligned interval test
Erect the Fence — convex hull
Convex Hull — Andrew's monotone chain
Minimum Area Rectangle, Valid Polygon area

The four building blocks

Orientation. sign(cross(a, b, c)) → +1 CCW, −1 CW, 0 collinear. Everything below is built on this.
Shoelace area. For polygon vertices in order, area = |Σ (x_i · y_next − x_next · y_i)| / 2. The sum is twice the signed area; sign reveals winding direction.
Segment intersection. Segments p1p2 and p3p4 cross iff the two orientation triples straddle: o1, o2 differ in sign and o3, o4 differ in sign. Handle collinear-overlap endpoints separately.
Rectangle overlap. Two axis-aligned rects overlap iff they overlap on both axes: ax1 < bx2 and bx1 < ax2 and ay1 < by2 and by1 < ay2 (strict = touching edges do not count).

Template — cross product + monotone-chain hull

def cross(a, b, c):
    # signed area of (b-a) x (c-a); >0 CCW, <0 CW, 0 collinear
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def convex_hull(points):
    # Andrew's monotone chain — O(n log n)
    pts = sorted(set(map(tuple, points)))   # sort by (x, then y), dedup
    if len(pts) <= 2: return pts

    def build(seq):
        hull = []
        for p in seq:
            # pop while last turn is NOT a left turn (<=0 drops collinear)
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
                hull.pop()
            hull.append(p)
        return hull

    lower = build(pts)
    upper = build(reversed(pts))
    return lower[:-1] + upper[:-1]   # drop shared endpoints

type Pt = [number, number];

const cross = (a: Pt, b: Pt, c: Pt): number =>
  (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);

function convexHull(points: Pt[]): Pt[] {
  const pts = [...points].sort((p, q) => p[0] - q[0] || p[1] - q[1]);
  if (pts.length <= 2) return pts;

  const build = (seq: Pt[]): Pt[] => {
    const h: Pt[] = [];
    for (const p of seq) {
      while (h.length >= 2 && cross(h[h.length - 2], h[h.length - 1], p) <= 0) h.pop();
      h.push(p);
    }
    return h;
  };

  const lower = build(pts);
  const upper = build([...pts].reverse());
  return [...lower.slice(0, -1), ...upper.slice(0, -1)];
}

Key trick — Max Points on a Line via slope hashing

Fix each point as an anchor, then bucket every other point by the direction from the anchor. Never store a float slope dy/dx — represent direction as a reduced integer pair (dy, dx) divided by their gcd, with a fixed sign convention so (1, 2) and (-1, -2) collapse to one key. The largest bucket (plus the anchor itself) is the answer for that anchor; take the max over all anchors. O(n²).

from math import gcd
from collections import defaultdict

def max_points(points):
    n = len(points)
    if n <= 2: return n
    best = 1
    for i in range(n):
        slopes = defaultdict(int)
        for j in range(n):
            if j == i: continue
            dy = points[j][1] - points[i][1]
            dx = points[j][0] - points[i][0]
            g = gcd(dy, dx) or 1          # avoid /0 if both are 0
            dy, dx = dy // g, dx // g
            if dx < 0 or (dx == 0 and dy < 0):  # normalize sign
                dy, dx = -dy, -dx
            slopes[(dy, dx)] += 1
        best = max(best, max(slopes.values(), default=0) + 1)
    return best

Complexity & gotchas

Cross product / orientation / shoelace / rect overlap: O(1) time and space each. Convex hull: O(n log n) time (dominated by the sort), O(n) space. Max points on a line: O(n²) time, O(n) extra space for the per-anchor buckets.
Prefer INTEGER cross products over float slopes. Comparing dy/dx as floats causes precision bugs; the cross product stays exact in integer arithmetic.
Vertical lines have undefined slope. The (dy, dx) reduced-pair key handles them naturally (e.g. (1, 0)) where a float slope would divide by zero.
Collinear points on the hull boundary need a tie rule. Pop on cross <= 0 to drop them (strict convex vertices only); use < 0 if the problem wants every boundary point kept (e.g. Erect the Fence).
Watch gcd(0, 0) when two points coincide — guard with or 1, or dedup the input first.
Shoelace requires vertices in consecutive order around the polygon; a scrambled order gives garbage. Take the absolute value for unsigned area.
Rectangle overlap: decide up front whether shared edges/corners count — use < (touching does not overlap) vs <= (touching counts).

Do two axis-aligned rectangles overlap with positive area?

→ Going deeper: Computational geometry on grids reuses matrix indexing. See Matrix & grid techniques.