To solve this problem, we need to determine the maximum number of points that lie on the same straight line given an array of points. The solution involves calculating slopes between points to identify lines and handling edge cases like duplicate points, vertical lines, and floating-point precision issues.

Approach

1. Edge Cases Handling: If there are fewer than 2 points, return the count of points directly.
2. Slope Calculation: For each point, compute the slope it forms with every other point. To avoid floating-point precision issues, represent slopes as reduced fractions (numerator and denominator in simplest form with a consistent sign).
3. Duplicate Points: Count duplicate points (same coordinates) as they contribute to all lines passing through the original point.
4. Vertical Lines: Represent vertical lines with a special key ('inf') since their slope is undefined.
5. Max Points on Line: For each point, track the maximum number of points on any line through it by counting slopes and adding duplicate points to this count.

Solution Code

import math
from collections import defaultdict

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

    max_p = 0

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

        for j in range(len(points)):
            if i == j:
                continue
            x2, y2 = points[j]

            # Count duplicate points
            if x1 == x2 and y1 == y2:
                duplicates += 1
                continue

            dy = y2 - y1
            dx = x2 - x1

            # Handle vertical lines (undefined slope)
            if dx == 0:
                key = ('inf',)
            else:
                # Reduce dy/dx to simplest form
                gcd_val = math.gcd(abs(dy), abs(dx))
                reduced_dy = dy // gcd_val
                reduced_dx = dx // gcd_val

                # Ensure consistent sign for the denominator
                if reduced_dx < 0:
                    reduced_dy *= -1
                    reduced_dx *= -1

                key = (reduced_dy, reduced_dx)

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

        # Total points on the line: duplicates + points with same slope
        total = duplicates + current_max
        max_p = max(max_p, total)

    return max_p

Explanation

1. Slope Representation: Slopes are represented as tuples of reduced fractions to avoid precision errors. For example, the slope 2/4 becomes (1,2), and -1/2 becomes (-1,2) (consistent sign for denominator).
2. Duplicate Points: Each duplicate point adds to all lines passing through the original point, so we count them separately and add to the slope count for each line.
3. Vertical Lines: Handled with a special key ('inf') since their slope is undefined.
4. Efficiency: The algorithm runs in O(n²) time complexity, where n is the number of points, as each point is compared to all other points once. This is optimal for this problem given the constraints.

This approach effectively handles all edge cases and ensures accurate results using integer arithmetic to avoid floating-point errors. It is robust and efficient for the given problem.

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