Chương trình đếm số điểm nằm trên một đường thẳng trong Python

Cho danh sách tọa độ [[x, y], ...] trên mặt phẳng Descartes. Tìm số điểm lớn nhất nằm trên cùng một đường thẳng.

Ví dụ: [[6,2],[8,3],[10,4],[1,1],[2,2],[6,6],[7,7]] → kết quả 4 (điểm [1,1], [2,2], [6,6], [7,7]).

Giải thuật (Duyệt từng điểm làm gốc + HashMap độ dốc)

1. Với mỗi điểm i, tính độ dốc đến mọi điểm j > i.
2. Dùng dictionary slopes đếm tần suất mỗi độ dốc. Xử lý riêng đường thẳng đứng (x1 == x2) gán slope = inf.
3. Đếm điểm trùng lặp (same).
4. Cập nhật kết quả: max(res, same + max(slopes.values())).

Ví dụ minh họa

class Solution:
    def solve(self, points):
        res = 0
        for i in range(len(points)):
            x1, y1 = points[i]
            slopes = {}
            same = 1
            for j in range(i + 1, len(points)):
                x2, y2 = points[j]
                if x2 == x1:
                    slopes[float('inf')] = slopes.get(float('inf'), 0) + 1
                elif x1 == x2 and y1 == y2:
                    same += 1
                else:
                    slope = (y2 - y1) / (x2 - x1)
                    slopes[slope] = slopes.get(slope, 0) + 1
            if slopes:
                res = max(res, same + max(slopes.values()))
        return res

ob = Solution()
coordinates = [[6,2],[8,3],[10,4],[1,1],[2,2],[6,6],[7,7]]
print(ob.solve(coordinates))  # Output: 4

Đầu vào / Đầu ra

Input: [[6,2],[8,3],[10,4],[1,1],[2,2],[6,6],[7,7]]

Output: 4