To solve this problem, we need to determine the maximum number of points that lie on the same straight line given a list of points. The key insight is to calculate the slope between each point and every other point, using a reduced fraction to avoid floating-point precision errors, and count how many points share the same slope (indicating they lie on the same line through the current point).

Approach

1. Edge Cases: If there are 0 or 1 points, return the count directly. If there are 2 points, they always lie on the same line, so return 2.
2. Slope Calculation: For each point, compute the slope to every other point. Represent the slope as a reduced fraction (numerator and denominator in simplest form) to avoid precision issues. Handle vertical lines (infinite slope) as a special case.
3. Count Slopes: Use a dictionary to count the frequency of each slope from the current point to others. Also, count points that are identical to the current point (since they lie on all lines through the current point).
4. Max Points: For each point, the maximum number of points on a line through it is the highest slope count plus the number of identical points. Track the maximum value across all points.

Solution Code

import math
from collections import defaultdict

def max_points(points):
    if len(points) <= 2:
        return len(points)

    max_count = 0

    for i in range(len(points)):
        x1, y1 = points[i]
        slope_counts = defaultdict(int)
        same_point = 1
        current_max = 0

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

            if dx == 0 and dy == 0:
                same_point += 1
                continue

            # Compute slope key
            if dx == 0:
                key = ('inf',)
            else:
                # Make denominator positive
                if dx < 0:
                    dy = -dy
                    dx = -dx
                g = math.gcd(abs(dy), abs(dx))
                reduced_dy = dy // g
                reduced_dx = dx // g
                key = (reduced_dy, reduced_dx)

            slope_counts[key] += 1
            current_max = max(current_max, slope_counts[key])

        # Update max_count with the total points on the best line through current point
        max_count = max(max_count, current_max + same_point)

    return max_count

Explanation

• Slope Representation: The slope between two points is represented as a tuple of reduced fractions. This avoids floating-point errors and ensures equivalent slopes have the same key.
• Vertical Lines: Handled using a special key ('inf',) since their slope is infinite.
• Same Points: Counted separately as they lie on all lines through the current point.
• Efficiency: For each point, we check all other points, leading to an O(n²) time complexity, which is acceptable for typical problem constraints.

This approach efficiently counts the maximum number of points on any line by leveraging slope calculations and dictionary-based frequency counting. It handles all edge cases, including identical points, vertical lines, and horizontal lines.

作者声明:本文包含人工智能生成内容。