Skip to content

3897. Count Number Of Trapezoids II

Array Hash Table Math Geometry

Problem - Count Number Of Trapezoids II

Hard

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 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 <= xi, yi <= 1000
  • All points are pairwise distinct.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        n = len(points)
        slope_to_intercept = defaultdict(list)
        mid_to_slope = defaultdict(list)
        result = 0

        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                dx = x2 - x1
                dy = y2 - y1

                if x2 == x1:
                    m = float('inf')
                    b = x1
                else:
                    m = (y2 - y1) / (x2 - x1)
                    b = (y1 * dx -x1 * dy) / dx

                mid = (x1 + x2) * 10000 + y2 + y1
                slope_to_intercept[m].append(b)
                mid_to_slope[mid].append(m)

        for sti in slope_to_intercept.values():
            if len(sti) == 1:
                continue

            count = defaultdict(int)
            for b_val in sti:
                count[b_val] += 1

            total_sum = 0
            for count in count.values():
                result += total_sum * count
                total_sum += count

        for mts in mid_to_slope.values():
            if len(mts) == 1:
                continue

            count = defaultdict(int)
            for m_val in mts:
                count[m_val] += 1

            total_sum = 0
            for count in count.values():
                result -= total_sum * count
                total_sum += count

        return result

Submission Stats:

  • Runtime: 944 ms (99.49%)
  • Memory: 68.5 MB (98.97%)