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

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 171阅读 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)