# 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)
还没有评论,来说两句吧...