3625. Count Number of Trapezoids II

[mah-shamim]

Topics: Array, Hash Table, Math, Geometry, Weekly Contest 459

You are given a 2D integer array points where points[i] = [xᵢ, yᵢ] represents the coordinates of the iᵗʰ point on the Cartesian plane.

Return the number of unique trapezoids that can be formed by choosing any four distinct points from points.

A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.

Example 1:

• Input: points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]
• Output: 2
• Explanation:
  
  • There are two distinct ways to pick four points that form a trapezoid:
    • The points [-3,2], [2,3], [3,2], [2,-3] form one trapezoid.
    • The points [2,3], [3,2], [3,0], [2,-3] form another trapezoid.

Example 2:

• Input: points = [[0,0],[1,0],[0,1],[2,1]]
• Output: 1
• Explanation:
  
  • There is only one trapezoid which can be formed.

Constraints:

• 4 <= points.length <= 500
• –1000 <= xᵢ, yᵢ <= 1000
• All points are pairwise distinct.

Hint:

1. Hash every point-pair by its reduced slope (dy,dx) (normalize with GCD and fix signs).
2. In each slope-bucket of size k, there are C(k,2) ways to pick two segments as the trapezoid's parallel bases.
3. Skip any base-pair that shares an endpoint since it would not form a quadrilateral.
4. Subtract one count for each parallelogram. Each parallelogram was counted once for each of its two parallel-side pairs, so after subtracting once, every quadrilateral with at least one pair of parallel sides, including parallelograms, contributes exactly one to the final total.
5. Final answer = total valid base-pairs minus parallelogram overcounts.

[mah-shamim]

We need to count trapezoids (quadrilaterals with at least one pair of parallel sides) from given points.

Approach:

• Precompute all point pairs (i, j) → each pair defines a segment.

• For each pair:

  • Compute the normalized slope (dy, dx); vertical lines treated separately.
  • Compute the normalized line equation (A, B, C) as the signature of that infinite line.
  • Compute the midpoint signature (x₁ + x₂, y₁ + y₂) without division (for parallelogram detection).

• Maintain:

  • cnt1[slope][lineSignature]
    → counts how many segments lie on the same infinite line with same slope
    → used to count pairs of parallel but non-collinear segments (candidate trapezoid bases).
  • cnt2[midpointSignature][slope]
    → counts segments sharing the same midpoint and slope
    → used to detect parallelograms (because diagonals of a parallelogram have same midpoint).

• Total trapezoid base pairs:

  • For each slope group:

    • If a slope has line-counts [c₁, c₂, ..., cₖ], add
      c₁*c₂ + c₁*c₃ + ... + c₁*cₖ + c₂*c₃ + ...
    • This counts every way to pick two segments on different parallel lines.

• Remove parallelogram overcounts:

  • For each midpoint group and slope group:

    • If counts are [c₁, c₂, ...], subtract pair combinations
      c₁*c₂ + c₁*c₃ + ...
    • Because parallelograms are counted twice, once per slope direction.

• Final result =
  Total parallel-segment pairs – parallelogram overcounts

• Return the computed trapezoid count.

Let's implement this solution in PHP: 3625. Count Number of Trapezoids II

<?php
/**
 * @param Integer[][] $points
 * @return Integer
 */
function countTrapezoids($points) {
    $n = count($points);
    if ($n < 4) return 0;

    // slope → (lineSignature → count)
    $cnt1 = [];
    // midpointSignature → (slopeSignature → count)
    $cnt2 = [];

    for ($i = 0; $i < $n; $i++) {
        [$x1, $y1] = $points[$i];
        for ($j = 0; $j < $i; $j++) {
            [$x2, $y2] = $points[$j];

            $dx = $x2 - $x1;
            $dy = $y2 - $y1;

            // ---- Normalize slope (dy, dx) ----
            if ($dx == 0) {
                $slope = "V,1"; // vertical
            } else {
                $g = gcd(abs($dx), abs($dy));
                $dy2 = intdiv($dy, $g);
                $dx2 = intdiv($dx, $g);
                // Fix sign: dx must be positive for uniqueness
                if ($dx2 < 0) {
                    $dx2 = -$dx2;
                    $dy2 = -$dy2;
                }
                $slope = $dy2 . "," . $dx2;
            }

            // ---- Normalize line (A,B,C): Ax+By+C=0 ----
            // For slope (dy,dx): line perpendicular has A = dy, B = -dx
            if ($dx == 0) {
                // vertical x = x1 → 1*x + 0*y - x1 = 0
                $A = 1; $B = 0; $C = -$x1;
            } else {
                // slope dy/dx → line eq: dy*x - dx*y + C = 0
                $A = $dy;
                $B = -$dx;
                // solve for C: A*x + B*y + C = 0 → C = -(Ax + By)
                $C = -($A * $x1 + $B * $y1);
            }

            $g = gcd(gcd(abs($A), abs($B)), abs($C));
            if ($g != 0) {
                $A = intdiv($A, $g);
                $B = intdiv($B, $g);
                $C = intdiv($C, $g);
            }
            // Fix sign for uniqueness
            if ($A < 0 || ($A == 0 && $B < 0)) {
                $A = -$A; $B = -$B; $C = -$C;
            }

            $lineKey = "$A,$B,$C";

            // ---- Update cnt1: slope → lines ----
            if (!isset($cnt1[$slope][$lineKey])) {
                $cnt1[$slope][$lineKey] = 0;
            }
            $cnt1[$slope][$lineKey]++;

            // ---- Update cnt2: midpoint+ slope = parallelogram detection ----
            $mx = $x1 + $x2;  // midpoint numerator only is enough
            $my = $y1 + $y2;

            $midKey = "$mx,$my";

            if (!isset($cnt2[$midKey][$slope])) {
                $cnt2[$midKey][$slope] = 0;
            }
            $cnt2[$midKey][$slope]++;
        }
    }

    $ans = 0;

    // ---- Count trapezoids: sum over slope-buckets ----
    foreach ($cnt1 as $slope => $lineMap) {
        $sum = 0;
        foreach ($lineMap as $cnt) {
            $ans += $sum * $cnt;
            $sum += $cnt;
        }
    }

    // ---- Subtract parallelograms: they were counted twice ----
    foreach ($cnt2 as $midKey => $slopes) {
        $sum = 0;
        foreach ($slopes as $cnt) {
            $ans -= $sum * $cnt;
            $sum += $cnt;
        }
    }

    return $ans;
}

// gcd
function gcd(int $a, int $b): int
{
    while ($b != 0) {
        [$a, $b] = [$b, $a % $b];
    }
    return $a;
}

// Test cases
echo countTrapezoids([[-3,2],[3,0],[2,3],[3,2],[2,-3]]) . "\n";                                                             // Output: 2
echo countTrapezoids([[0,0],[1,0],[0,1],[2,1]]) . "\n";                                                                     // Output: 1
echo countTrapezoids([[82,7],[82,-9],[82,-52],[82,78]]) . "\n";                                                             // Output: 0
echo countTrapezoids([[83,-25],[74,11],[-65,-25],[33,-25],[17,-25],[1,30],[-84,-25],[1,-25],[1,-92],[-87,13]]) . "\n";      // Output: 0
?>

Explanation:

• A trapezoid is any convex quadrilateral with at least one pair of parallel sides.

• Two segments can serve as parallel bases of a trapezoid only if:

  • They have equal slope.
  • They lie on different lines (not collinear).
  • They share no endpoints.

• The slope & line normal form (A, B, C) uniquely identify such conditions.

• Counting two segments in different collinear buckets ensures endpoints are distinct and segments are on different parallel lines.

• Using combinations sum += previousCount * currentCount efficiently counts all unordered segment pairs.

• Parallelograms:

  • A parallelogram will be counted once for each slope direction (because it has two pairs of parallel sides).
  • Diagonals of a parallelogram always share the same midpoint → we use this to detect them.
  • Subtracting combinations from midpoint groups removes the extra count.

• The midpoint method is guaranteed correct because:

  • Only diagonals share midpoints, and diagonals correspond to segment pairs in cnt2.

• Normalizing slope and line equations ensures:

  • No floating-point errors.
  • All equivalent slopes/lines map to exactly one hash key.

• Time complexity:

  • O(n²) to process all point pairs.
  • Works for n ≤ 500 (≈125k pairs) easily.

• The final value represents all unique quadrilaterals having at least one pair of parallel sides → exactly the definition of a trapezoid.

[mah-shamim]

Thanks for solving the problem of "Count Number of Trapezoids II"

[mah-shamim]

Thanks