You are given a 2D integer array points where points[i] = [xi, yi] represents the coordinates of the ith point on the Cartesian plane. Return the number of unique trapezoids that can be formed by choosing any four distinct points from points. A tra

countTrapezoids.js

/**
 * Count the number of unique trapezoids that can be formed
 * from a set of points on the Cartesian plane.
 *
 * @param {number[][]} points - Array of [x, y] coordinates
 * @return {number} - Number of trapezoids
 */
var countTrapezoids = function(points) {
    const t = new Map(); // Tracks lines grouped by slope (normalized)
    const v = new Map(); // Tracks lines grouped by raw vector direction
    const n = points.length;

    /**
     * Helper to add a line into a map structure.
     * Each map key corresponds to a slope/direction,
     * and the inner map tracks distinct line positions (via intercept).
     */
    function add(map, key, intercept) {
        if (!map.has(key)) map.set(key, new Map());
        const inner = map.get(key);
        inner.set(intercept, (inner.get(intercept) || 0) + 1);
    }

    // Iterate over all pairs of points to define lines
    for (let i = 0; i < n; i++) {
        let [x1, y1] = points[i];
        for (let j = i + 1; j < n; j++) {
            let [x2, y2] = points[j];

            // Direction vector of the line
            let dx = x2 - x1;
            let dy = y2 - y1;

            // Normalize direction: ensure dx >= 0 (or dy >= 0 if vertical)
            if (dx < 0 || (dx === 0 && dy < 0)) {
                dx = -dx;
                dy = -dy;
            }

            // Reduce direction vector to simplest integer ratio
            let g = gcd(dx, Math.abs(dy));
            let sx = dx / g; // normalized slope numerator
            let sy = dy / g; // normalized slope denominator

            // Compute a "line descriptor" (like intercept) to distinguish parallel lines
            // Formula: sx*y - sy*x is invariant for points on the same line
            let intercept = sx * y1 - sy * x1;

            // Create compact integer keys for slope and direction
            let keySlope = (sx << 12) | (sy + 2000); // slope-based key
            let keyVector = (dx << 12) | (dy + 2000); // raw vector-based key

            // Add line to both maps
            add(t, keySlope, intercept);
            add(v, keyVector, intercept);
        }
    }

    // Count trapezoids:
    // - count(t): number of pairs of parallel lines
    // - count(v): number of duplicate lines (same vector & intercept)
    //   divide by 2 because each line is counted twice
    return count(t) - Math.floor(count(v) / 2);
};

/**
 * Compute greatest common divisor (Euclidean algorithm).
 */
function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b !== 0) {
        let tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

/**
 * Count the number of unordered pairs of distinct lines
 * within each slope/direction group.
 *
 * For each group:
 *   - total = number of lines in group
 *   - ans += sum over val * (remaining lines)
 */
function count(map) {
    let ans = 0;

    for (let inner of map.values()) {
        // Total lines in this slope group
        let total = 0;
        for (let val of inner.values()) total += val;

        // Count pairs of distinct lines
        let remaining = total;
        for (let val of inner.values()) {
            remaining -= val;
            ans += val * remaining;
        }
    }
    return ans;
}