Shapes / Geometry

"Area/perimeter/volume of geometric shapes, union/intersection of shapes, packing, tiling, cutting stock."

Deep Dive Tutorial

Shape problems seem diverse but use the same small set of geometric primitives: distance between points, triangle area via cross product, overlap detection via axis separation, and polygon area via shoelace. Once you see which primitive applies, the code is mechanical.

Geometric Primitives

Core geometry formulas

// Distance between two points
const dist = (a, b) => Math.sqrt((b[0]-a[0])**2 + (b[1]-a[1])**2);
const dist2 = (a, b) => (b[0]-a[0])**2 + (b[1]-a[1])**2; // squared (avoids sqrt)

// Cross product of vectors (b-a) × (c-a)
// > 0: counterclockwise, < 0: clockwise, = 0: collinear
const cross = (a, b, c) =>
    (b[0]-a[0]) * (c[1]-a[1]) - (b[1]-a[1]) * (c[0]-a[0]);

// Triangle area from 3 points (shoelace / half cross product)
const triArea = (a, b, c) => Math.abs(cross(a, b, c)) / 2;

// Polygon area (shoelace formula)
function polyArea(pts) {
    let area = 0;
    const n = pts.length;
    for (let i = 0; i < n; i++) {
        const j = (i + 1) % n;
        area += pts[i][0] * pts[j][1] - pts[j][0] * pts[i][1];
    }
    return Math.abs(area) / 2;
}

// Triangle inequality (valid triangle)
const validTriangle = (a, b, c) => a+b>c && b+c>a && a+c>b;

// Point inside axis-aligned rectangle
const inRect = (p, x1, y1, x2, y2) =>
    p[0]>=x1 && p[0]<=x2 && p[1]>=y1 && p[1]<=y2;

// Two axis-aligned rectangles overlap (NOT just touch)
const rectsOverlap = (ax1,ay1,ax2,ay2, bx1,by1,bx2,by2) =>
    ax1 < bx2 && bx1 < ax2 && ay1 < by2 && by1 < ay2;

Triangle Problems

Problem type	Key check	Formula
Valid triangle	Triangle inequality	a+b>c && b+c>a && a+c>b
Max perimeter triangle	Sort, check last 3	If a[n-3]+a[n-2]>a[n-1], answer is sum
Collinear points	Cross product = 0	cross(a,b,c) === 0
Triangle area	Shoelace/cross	\|cross(a,b,c)\| / 2
Triangle type	Compare squared sides	a²+b²=c² (right), a²+b²<c² (obtuse)

Rectangle Problems

Rectangle union area (two rectangles)

// Area of union of two rectangles (inclusion-exclusion)
function rectangleArea(rec1, rec2) {
    const MOD = 1_000_000_007n;
    const area = (r) => BigInt(r[2]-r[0]) * BigInt(r[3]-r[1]);
    const intersectX1 = Math.max(rec1[0], rec2[0]);
    const intersectY1 = Math.max(rec1[1], rec2[1]);
    const intersectX2 = Math.min(rec1[2], rec2[2]);
    const intersectY2 = Math.min(rec1[3], rec2[3]);
    const intersect =
        intersectX1 < intersectX2 && intersectY1 < intersectY2
        ? BigInt(intersectX2-intersectX1) * BigInt(intersectY2-intersectY1)
        : 0n;
    return Number((area(rec1) + area(rec2) - intersect) % MOD);
}

Circle Problems

lightbulb

Two circles intersect/overlap if: dist(c1, c2) < r1 + r2
One inside other if: dist(c1, c2) < |r1 - r2|
Circle contains point: dist(center, point) <= radius

Always compare squared distances to avoid floating point: dist² < (r1+r2)²

Circle chain explosion — BFS on circle intersections

// Given circles, if you detonate one, all intersecting circles also detonate
// Find: max circles detonated by detonating one
function maximumDetonation(bombs) {
    const n = bombs.length;
    // Build directed graph: a can trigger b if dist(a,b) <= r_a
    const graph = Array.from({length:n}, ()=>[]);
    for (let i = 0; i < n; i++)
        for (let j = 0; j < n; j++) {
            if (i===j) continue;
            const [x1,y1,r1] = bombs[i], [x2,y2] = bombs[j];
            const d2 = (x2-x1)**2 + (y2-y1)**2;
            if (d2 <= r1*r1) graph[i].push(j); // i triggers j
        }
    // BFS from each bomb
    let ans = 0;
    for (let start = 0; start < n; start++) {
        const visited = new Set([start]);
        const q = [start];
        while (q.length) {
            const u = q.shift();
            for (const v of graph[u])
                if (!visited.has(v)) { visited.add(v); q.push(v); }
        }
        ans = Math.max(ans, visited.size);
    }
    return ans;
}