Created
December 3, 2025 18:47
-
-
Save tatsuyax25/795313988cd47f1baccd8fb2c7b216ee to your computer and use it in GitHub Desktop.
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * 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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment