Welcome to Subscribe On Youtube

3625. Count Number of Trapezoids II

Description

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

Solution 1

  • class Solution {
    public int countTrapezoids(int[][] points) {
        int n = points.length;
        Map<Double, Map<Double, Integer>> cnt1 = new HashMap<>(n * n);
        Map<Integer, Map<Double, Integer>> cnt2 = new HashMap<>(n * n);

        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = 0; j < i; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                int dx = x2 - x1, dy = y2 - y1;
                double k = dx == 0 ? Double.MAX_VALUE : 1.0 * dy / dx;
                double b = dx == 0 ? x1 : 1.0 * (y1 * dx - x1 * dy) / dx;
                if (k == -0.0) {
                    k = 0.0;
                }
                if (b == -0.0) {
                    b = 0.0;
                }
                cnt1.computeIfAbsent(k, _ -> new HashMap<>()).merge(b, 1, Integer::sum);
                int p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
                cnt2.computeIfAbsent(p, _ -> new HashMap<>()).merge(k, 1, Integer::sum);
            }
        }

        int ans = 0;
        for (var e : cnt1.values()) {
            int s = 0;
            for (int t : e.values()) {
                ans += s * t;
                s += t;
            }
        }
        for (var e : cnt2.values()) {
            int s = 0;
            for (int t : e.values()) {
                ans -= s * t;
                s += t;
            }
        }
        return ans;
    }
}


  • class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        int n = points.size();
        unordered_map<double, unordered_map<double, int>> cnt1;
        unordered_map<int, unordered_map<double, int>> cnt2;

        cnt1.reserve(n * n);
        cnt2.reserve(n * n);

        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = 0; j < i; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                int dx = x2 - x1, dy = y2 - y1;
                double k = (dx == 0 ? 1e9 : 1.0 * dy / dx);
                double b = (dx == 0 ? x1 : 1.0 * (1LL * y1 * dx - 1LL * x1 * dy) / dx);

                cnt1[k][b] += 1;
                int p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
                cnt2[p][k] += 1;
            }
        }

        int ans = 0;
        for (auto& [_, e] : cnt1) {
            int s = 0;
            for (auto& [_, t] : e) {
                ans += s * t;
                s += t;
            }
        }
        for (auto& [_, e] : cnt2) {
            int s = 0;
            for (auto& [_, t] : e) {
                ans -= s * t;
                s += t;
            }
        }
        return ans;
    }
};


  • class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        n = len(points)

        # cnt1: k -> (b -> count)
        cnt1: dict[float, dict[float, int]] = defaultdict(lambda: defaultdict(int))
        # cnt2: p -> (k -> count)
        cnt2: dict[int, dict[float, int]] = defaultdict(lambda: defaultdict(int))

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

                if dx == 0:
                    k = 1e9
                    b = x1
                else:
                    k = dy / dx
                    b = (y1 * dx - x1 * dy) / dx

                cnt1[k][b] += 1

                p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000)
                cnt2[p][k] += 1

        ans = 0

        for e in cnt1.values():
            s = 0
            for t in e.values():
                ans += s * t
                s += t

        for e in cnt2.values():
            s = 0
            for t in e.values():
                ans -= s * t
                s += t

        return ans


  • func countTrapezoids(points [][]int) int {
	n := len(points)
	cnt1 := make(map[float64]map[float64]int, n*n)
	cnt2 := make(map[int]map[float64]int, n*n)

	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]
		for j := 0; j < i; j++ {
			x2, y2 := points[j][0], points[j][1]
			dx, dy := x2-x1, y2-y1

			var k, b float64
			if dx == 0 {
				k = 1e9
				b = float64(x1)
			} else {
				k = float64(dy) / float64(dx)
				b = float64(int64(y1)*int64(dx)-int64(x1)*int64(dy)) / float64(dx)
			}

			if cnt1[k] == nil {
				cnt1[k] = make(map[float64]int)
			}
			cnt1[k][b]++

			p := (x1+x2+2000)*4000 + (y1 + y2 + 2000)
			if cnt2[p] == nil {
				cnt2[p] = make(map[float64]int)
			}
			cnt2[p][k]++
		}
	}

	ans := 0
	for _, e := range cnt1 {
		s := 0
		for _, t := range e {
			ans += s * t
			s += t
		}
	}
	for _, e := range cnt2 {
		s := 0
		for _, t := range e {
			ans -= s * t
			s += t
		}
	}
	return ans
}


  • function countTrapezoids(points: number[][]): number {
    const n = points.length;

    const cnt1: Map<number, Map<number, number>> = new Map();
    const cnt2: Map<number, Map<number, number>> = new Map();

    for (let i = 0; i < n; i++) {
        const [x1, y1] = points[i];
        for (let j = 0; j < i; j++) {
            const [x2, y2] = points[j];
            const [dx, dy] = [x2 - x1, y2 - y1];

            const k = dx === 0 ? 1e9 : dy / dx;
            const b = dx === 0 ? x1 : (y1 * dx - x1 * dy) / dx;

            if (!cnt1.has(k)) {
                cnt1.set(k, new Map());
            }
            const mapB = cnt1.get(k)!;
            mapB.set(b, (mapB.get(b) || 0) + 1);

            const p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);

            if (!cnt2.has(p)) {
                cnt2.set(p, new Map());
            }
            const mapK = cnt2.get(p)!;
            mapK.set(k, (mapK.get(k) || 0) + 1);
        }
    }

    let ans = 0;
    for (const e of cnt1.values()) {
        let s = 0;
        for (const t of e.values()) {
            ans += s * t;
            s += t;
        }
    }
    for (const e of cnt2.values()) {
        let s = 0;
        for (const t of e.values()) {
            ans -= s * t;
            s += t;
        }
    }

    return ans;
}

All Problems

All Solutions