n points on a 2D plane, find the maximum number of points that lie on the same straight line(python)

我就是我 2022-05-17 03:43 95阅读 0赞

# Definition for a point.
    # 寻找最大共线的点的数量
    class Point:
        def __init__(self,a=0.0,b=0.0):
            self.x = float(a)
            self.y = float(b)
    class Solution:
        # 求取两点间的斜率
        def compute_rate(self,point1,point2):
            rate_x = float(point1.x) - float(point2.x)
            rate_y = float(point1.y) - float(point2.y)
            if abs(rate_x) < 10**(-9):
                return "inf"
            else:
                return float(rate_y)/float(rate_x)
        # 主要功能函数
        def judge_linepoint(self,points):
            # 小于两个点，没必要判断
            if len(points) < 2:
                return len(points)
            else:
                results = [] # 保存结果
                for i in range(len(points)):
                    dict_temp = {} # map，keys为经过一个点的所有直线，values为该直线共享多少的点
                    points_copy = points[:] # 拷贝操作
                    max_val = 0
                    points_copy.pop(i) # 剩余的其他点
                    for j in range(len(points_copy)):
                        # 计算斜率
                        rate = self.compute_rate(points[i],points_copy[j])
                        # 斜率不在键中，添加新的直线到字典
                        if rate not in dict_temp.keys():
                            dict_temp[rate] = 1
                        # 已经在了，累加数量
                        else:
                            dict_temp[rate] += 1
                        # 求共线最多的点
                        if dict_temp[rate] > max_val:
                            max_val = dict_temp[rate]
                    # 保存经过每一点的最大共线点数量
                    results.append(max_val)    
                return max(results) + 1
    a1 = Point(1,1)
    a2 = Point(2,1)
    a3 = Point(2,2)
    a4 = Point(3,3)
    a5 = Point(1,0)
    a6 = Point(1,2)
    a7 = Point(1,10)
    a8 = Point(1,10)
    a9 = Point()
    points = [a1,a2,a3,a4,a5,a6,a7,a8,a9]
    S = Solution()
    S.judge_linepoint(points)