Shapes & 2D Geometry

// 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;

// 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);
}

// 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;
}