Leetcode 3625. Count Number of Trapezoids II

def count_trapezoids(points):
    """
    Brute force approach: Check all 4-point combinations to count trapezoids.
    A trapezoid has at least one pair of parallel sides (same slope).
    Time: O(n^4), Space: O(1)
    """
    n = len(points)
    count = 0
    
    # Try all combinations of 4 points
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                for m in range(k + 1, n):
                    # Get the 4 points
                    p1, p2, p3, p4 = points[i], points[j], points[k], points[m]
                    
                    # Check if these 4 points form a trapezoid
                    if is_trapezoid(p1, p2, p3, p4):
                        count += 1
    
    return count
def is_trapezoid(p1, p2, p3, p4):
    """
    Check if 4 points form a trapezoid.
    Must have at least one pair of parallel sides and be convex.
    """
    # Calculate all 6 possible line segment slopes
    # Sides: (p1,p2), (p2,p3), (p3,p4), (p4,p1)
    # Diagonals: (p1,p3), (p2,p4)
    
    slopes = []
    pairs = [(p1, p2), (p2, p3), (p3, p4), (p4, p1), (p1, p3), (p2, p4)]
    
    for pt1, pt2 in pairs:
        slope = get_slope(pt1, pt2)
        slopes.append(slope)
    
    # Check if opposite sides are parallel (trapezoid condition)
    # Sides: 0=(p1,p2), 1=(p2,p3), 2=(p3,p4), 3=(p4,p1)
    side1_parallel_side3 = slopes[0] == slopes[2]  # (p1,p2) || (p3,p4)
    side2_parallel_side4 = slopes[1] == slopes[3]  # (p2,p3) || (p4,p1)
    
    has_parallel_sides = side1_parallel_side3 or side2_parallel_side4
    
    if not has_parallel_sides:
        return False
    
    # Check convexity: no point should be inside triangle formed by other 3
    if not is_convex_quad(p1, p2, p3, p4):
        return False
    
    return True
def get_slope(p1, p2):
    """
    Calculate slope between two points.
    Returns tuple (dy, dx) in reduced form to handle vertical lines.
    """
    dx = p2[0] - p1[0]
    dy = p2[1] - p1[1]
    
    if dx == 0:
        return (1, 0)  # Vertical line
    if dy == 0:
        return (0, 1)  # Horizontal line
    
    # Reduce to lowest terms using GCD
    from math import gcd
    g = gcd(abs(dy), abs(dx))
    dy, dx = dy // g, dx // g
    
    # Normalize sign
    if dx < 0:
        dy, dx = -dy, -dx
    
    return (dy, dx)
def is_convex_quad(p1, p2, p3, p4):
    """
    Check if quadrilateral is convex using cross products.
    All cross products should have the same sign.
    """
    def cross_product_sign(a, b, c):
        # Cross product of vectors (b-a) and (c-b)
        return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
    
    # Check all 4 vertices
    signs = []
    vertices = [p1, p2, p3, p4]
    
    for i in range(4):
        a = vertices[i]
        b = vertices[(i + 1) % 4]
        c = vertices[(i + 2) % 4]
        cp = cross_product_sign(a, b, c)
        signs.append(cp)
    
    # All cross products should have same sign (all positive or all negative)
    all_positive = all(s > 0 for s in signs)
    all_negative = all(s < 0 for s in signs)
    
    return all_positive or all_negative

from math import gcd
from collections import defaultdict
def count_trapezoids(points):
    """
    Count trapezoids formed by 4-point subsets with at least one pair of parallel sides.
    Uses slope grouping to find parallel segments in O(n^2) time.
    """
    n = len(points)
    if n < 4:
        return 0
    
    # Group point-pairs by slope (reduced to lowest terms)
    slope_groups = defaultdict(list)
    
    # Generate all point-pairs and group by slope
    for i in range(n):
        for j in range(i + 1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            
            # Calculate slope as reduced fraction (dy, dx)
            dx = x2 - x1
            dy = y2 - y1
            
            # Reduce to lowest terms
            if dx == 0:
                slope = (1, 0)  # Vertical line
            elif dy == 0:
                slope = (0, 1)  # Horizontal line
            else:
                g = gcd(abs(dx), abs(dy))
                dx //= g
                dy //= g
                # Normalize sign: make dx positive
                if dx < 0:
                    dx, dy = -dx, -dy
                slope = (dy, dx)
            
            # Store pair with its slope
            slope_groups[slope].append((i, j))
    
    trapezoid_count = 0
    
    # For each slope group, count disjoint pairs
    for slope, pairs in slope_groups.items():
        m = len(pairs)
        
        # Count combinations of disjoint pairs
        for p1 in range(m):
            i1, j1 = pairs[p1]
            
            for p2 in range(p1 + 1, m):
                i2, j2 = pairs[p2]
                
                # Check if pairs are disjoint (no shared points)
                if i1 != i2 and i1 != j2 and j1 != i2 and j1 != j2:
                    # Check not collinear (all 4 points)
                    x1, y1 = points[i1]
                    x2, y2 = points[j1]
                    x3, y3 = points[i2]
                    x4, y4 = points[j2]
                    
                    # Use cross product to check collinearity
                    # Points are collinear if area of triangle is 0
                    area1 = abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1))
                    area2 = abs((x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1))
                    
                    if area1 > 0 and area2 > 0:
                        trapezoid_count += 1
    
    return trapezoid_count