Count Number of Trapezoids I
You receive a 2D integer array points, where points[i] = [x i, y i ] represents the coordinates of the i th point on the Cartesian plane.
A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.
Produce the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from points.
Since the answer may be very large, produce it modulo 10^9 + 7.
Input: points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
Output: 3
Explanation: There are three distinct ways to pick four points that form a horizontal trapezoid:
-
Using points
[1,0],[2,0],[3,2], and[2,2]. -
Using points
[2,0],[3,0],[3,2], and[2,2]. -
Using points
[1,0],[3,0],[3,2], and[2,2].
Input: points = [[0,0],[1,0],[0,1],[2,1]]
Output: 1
Explanation: There is only one horizontal trapezoid that can be formed.
Constraints
4 <= points.length <= 10^5–10^8 <= x i, y i <= 10^8- All points are pairwise distinct.
Did this problem appear in one of your interviews?
Responses stay private.