To solve this problem, we need to find the maximum number of points that lie on the same straight line in a 2D plane. The key challenge is to handle slopes accurately without floating-point precision issues and account for duplicate points.

Approach

1. Edge Cases: If there are 0, 1, or 2 points, the answer is the number of points itself since any two points form a line.
2. Slope Calculation: For each point, calculate the slope of the line formed with every other point. To avoid floating-point errors, represent the slope as a reduced fraction (dy, dx) where dy and dx are coprime integers. Normalize the fraction to ensure a unique key for each slope.
3. Duplicate Points: Count points that are the same as the current point since they lie on every line through the current point.
4. Max Points on Line: For each point, track the frequency of each slope. The maximum number of points on a line through the current point is the highest frequency of any slope plus the count of duplicates plus 1 (the current point itself).

Solution Code

import math
from collections import defaultdict

def get_slope_key(dx, dy):
    if dx == 0 and dy == 0:
        return None  # Same point
    g = math.gcd(abs(dx), abs(dy))
    reduced_dx = dx // g
    reduced_dy = dy // g

    # Normalize sign: ensure dx is positive, or dy positive if dx is zero
    if reduced_dx < 0:
        reduced_dx *= -1
        reduced_dy *= -1
    if reduced_dx == 0:
        if reduced_dy < 0:
            reduced_dy *= -1

    return (reduced_dy, reduced_dx)

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

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

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

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

            key = get_slope_key(dx, dy)
            slope_counts[key] += 1
            if slope_counts[key] > current_max:
                current_max = slope_counts[key]

        total = current_max + duplicates + 1
        if total > max_p:
            max_p = total

    return max_p

Explanation

1. Slope Normalization: The get_slope_key function reduces the slope (dy, dx) to its simplest form using the greatest common divr (gcd). It ensures the key is unique by normalizing the sign (dx positive, or dy positive if dx is zero).
2. Counting Slopes: For each point, we use a dictionary to count how many times each slope occurs. This helps identify the line with the most points through the current point.
3. Handling Duplicates: Duplicate points are added to the total count of points on any line through the current point, as they lie on all such lines.

This approach efficiently finds the maximum number of points on a line with a time complexity of O(n²), which is optimal for this problem. The space complexity is O(n) for storing slope counts and duplicates.

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