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 163阅读 0赞
  1. # Definition for a point.
  2. # 寻找最大共线的点的数量
  3. class Point:
  4. def __init__(self,a=0.0,b=0.0):
  5. self.x = float(a)
  6. self.y = float(b)
  7. class Solution:
  8. # 求取两点间的斜率
  9. def compute_rate(self,point1,point2):
  10. rate_x = float(point1.x) - float(point2.x)
  11. rate_y = float(point1.y) - float(point2.y)
  12. if abs(rate_x) < 10**(-9):
  13. return "inf"
  14. else:
  15. return float(rate_y)/float(rate_x)
  16. # 主要功能函数
  17. def judge_linepoint(self,points):
  18. # 小于两个点,没必要判断
  19. if len(points) < 2:
  20. return len(points)
  21. else:
  22. results = [] # 保存结果
  23. for i in range(len(points)):
  24. dict_temp = {} # map,keys为经过一个点的所有直线,values为该直线共享多少的点
  25. points_copy = points[:] # 拷贝操作
  26. max_val = 0
  27. points_copy.pop(i) # 剩余的其他点
  28. for j in range(len(points_copy)):
  29. # 计算斜率
  30. rate = self.compute_rate(points[i],points_copy[j])
  31. # 斜率不在键中,添加新的直线到字典
  32. if rate not in dict_temp.keys():
  33. dict_temp[rate] = 1
  34. # 已经在了,累加数量
  35. else:
  36. dict_temp[rate] += 1
  37. # 求共线最多的点
  38. if dict_temp[rate] > max_val:
  39. max_val = dict_temp[rate]
  40. # 保存经过每一点的最大共线点数量
  41. results.append(max_val)
  42. return max(results) + 1
  43. a1 = Point(1,1)
  44. a2 = Point(2,1)
  45. a3 = Point(2,2)
  46. a4 = Point(3,3)
  47. a5 = Point(1,0)
  48. a6 = Point(1,2)
  49. a7 = Point(1,10)
  50. a8 = Point(1,10)
  51. a9 = Point()
  52. points = [a1,a2,a3,a4,a5,a6,a7,a8,a9]
  53. S = Solution()
  54. S.judge_linepoint(points)

发表评论

表情:
评论列表 (有 0 条评论,163人围观)

还没有评论,来说两句吧...

相关阅读