3886. Count Number of Trapezoids I

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # Group points by y-coordinate
        from collections import defaultdict
        y_groups = defaultdict(list)
        for x, y in points:
            y_groups[y].append(x)
        
        # Count pairs of line segments that share same y-coordinate (parallel horizontal lines)
        # For each y with k points, we have C(k,2) = k*(k-1)/2 horizontal segments
        # We need to pick 2 horizontal segments from different y-values OR
        # pick 2 points from one y and 2 from another
        
        # Count horizontal line pairs for each y
        segment_counts = []
        for y, x_list in y_groups.items():
            k = len(x_list)
            if k >= 2:
                # C(k, 2) line segments
                segment_counts.append(k * (k - 1) // 2)
        
        # Answer is C(total_segments, 2) + sum of C(segment_count, 2) for y's with 4+ points
        # Actually, we need pairs of horizontal segments from different y's
        # Plus, if 4 points on same y, we can form trapezoid with 2 segments from same y
        
        # For trapezoid: pick 2 segments from (possibly same or different) y-values
        # Each segment defined by 2 points
        
        total_segments = sum(segment_counts)
        
        # Pick 2 segments: C(total, 2) = total*(total-1)/2
        # But segments from same y can't form trapezoid with each other (unless 4+ pts on same y)
        
        # Total ways to pick 2 segments
        total_pairs = total_segments * (total_segments - 1) // 2
        
        # Subtract pairs from same y (unless they share 0 points)
        for y, x_list in y_groups.items():
            k = len(x_list)
            seg_count = k * (k - 1) // 2
            # Pairs of segments from same y
            same_y_pairs = seg_count * (seg_count - 1) // 2
            total_pairs -= same_y_pairs
        
        return total_pairs % MOD