Chương trình đếm số điểm nằm trên một dòng bằng Python

Giả sử chúng ta có một danh sách các tọa độ. Mỗi tọa độ có hai giá trị x và y, biểu diễn một điểm trên mặt phẳng Descartes. Bây giờ, hãy tìm số điểm tối đa nằm trên một số dòng.

Vì vậy, nếu đầu vào giống như tọa độ =[[6, 2], [8, 3], [10, 4], [1, 1], [2, 2], [6, 6], [7, 7 ]], thì đầu ra sẽ là 4, vì các điểm là [1, 1], [2, 2], [6, 6], [7, 7]] nằm trên một dòng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=0

• đối với tôi trong phạm vi từ 0 đến kích thước của danh sách điểm, hãy thực hiện

  • (x1, y1):=điểm [i]

  • dốc:=một bản đồ mới

  • giống nhau:=1

  • đối với j trong phạm vi i + 1 đến kích thước của điểm, thực hiện

    • (x2, y2):=điểm [j]

    • nếu x2 giống với x1, thì

      • độ dốc [inf]:=1 + (độ dốc [inf] nếu thoát ra ngoài 0)

    • ngược lại khi x1 giống x2 và y1 giống y2 thì

      • giống nhau:=same + 1

    • nếu không,

      • độ dốc:=(y2 - y1) / (x2 - x1)

      • độ dốc [độ dốc]:=1 + (độ dốc [độ dốc] nếu thoát ra ngoài 0)

  • nếu dốc không trống thì

    • res:=tối đa của res và (cùng + tối đa của danh sách tất cả các giá trị của độ dốc)

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution:
   def solve(self, points):
      res = 0
      for i in range(len(points)):
         x1, y1 = points[i][0], points[i][1]
         slopes = {}
         same = 1
         for j in range(i + 1, len(points)):
            x2, y2 = points[j][0], points[j][1]
            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))

Đầu vào

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

Đầu ra

4