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 use slopes between pairs of points to identify collinear points, while handling edge cases like duplicate points, vertical lines, and horizontal lines.
Approach
- Edge Cases Handling: If there are 0 or 1 points, return the count directly as all points are trivially collinear.
- Slope Calculation: For each point, calculate the slope it forms with every other point. To avoid floating-point errors, represent slopes as reduced fractions (numerator and denominator in their simplest form with a consistent sign).
- Duplicate Points: Count duplicate points since they lie on every line through the original point.
- Vertical Lines: Use a unique key (like 'inf') to represent vertical lines (undefined slope).
- Max Collinear Points: For each point, the maximum number of collinear points is the count of points with the same slope plus duplicates plus the point itself. Track the global maximum across all points.
Solution Code
import math
from typing import List
def max_points(points: List[List[int]]) -> int:
if len(points) <= 1:
return len(points)
max_count = 0
for i in range(len(points)):
x1, y1 = points[i]
slope_dict = {}
duplicates = 0
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:
duplicates += 1
continue
# Compute the slope key
if dx == 0:
key = ('inf',)
else:
g = math.gcd(abs(dy), abs(dx))
reduced_dy = dy // g
reduced_dx = dx // g
# Ensure denominator is positive
if reduced_dx < 0:
reduced_dy *= -1
reduced_dx *= -1
key = (reduced_dy, reduced_dx)
# Update slope count
slope_dict[key] = slope_dict.get(key, 0) + 1
current_max = max(current_max, slope_dict[key])
# Total points for current line: current_max (same slope) + duplicates + 1 (current point)
total = current_max + duplicates + 1
max_count = max(max_count, total)
return max_count
Explanation
- Slope Representation: By using reduced fractions (as tuples), we avoid floating-point precision issues. For example, the slope 2/4 is represented as (1,2), and -1/2 as (-1,2) (consistent sign for denominator).
- Duplicate Points: These are counted separately because they lie on every line through the original point.
- Vertical Lines: Handled with a unique key ('inf') since their slope is undefined.
- Efficiency: The algorithm runs in O(n²) time complexity (for each point, we compare with all others) and O(n) space complexity (for storing slope counts per point). This is optimal for this problem given the constraints.
This approach ensures that we correctly identify the maximum number of collinear points by leveraging slope calculations and handling all edge cases.

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