পাইথনে একটি লাইনে থাকা পয়েন্টের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে স্থানাঙ্কের একটি তালিকা আছে। প্রতিটি স্থানাঙ্কের দুটি মান x এবং y রয়েছে যা কার্টেসিয়ান সমতলে একটি বিন্দুকে প্রতিনিধিত্ব করে। এখন কোন লাইনে থাকা সর্বোচ্চ সংখ্যক পয়েন্ট খুঁজুন।

সুতরাং, যদি ইনপুট স্থানাঙ্কের মত হয় =[[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7 ]], তাহলে আউটপুট হবে 4, যেমন পয়েন্টগুলি হল [1, 1], [2, 2], [6, 6], [7, 7]] যেগুলি একটি লাইনের উপর অবস্থিত৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• res :=0

• পয়েন্ট তালিকার আকার 0 থেকে সীমার জন্য, করুন

  • (x1, y1) :=পয়েন্ট[i]

  • ঢাল :=একটি নতুন মানচিত্র

  • একই :=1

  • j রেঞ্জ i + 1 থেকে পয়েন্টের আকারের জন্য, করুন

    • (x2, y2) :=পয়েন্ট[j]

    • যদি x2 x1 এর মত হয়, তাহলে

      • slopes[inf] :=1 + (ঢাল [inf] যদি প্রস্থান হয় অন্যথায় 0)

    • অন্যথায় যখন x1 x2 এর মত এবং y1 y2 এর সমান, তখন

      • একই :=একই + 1

    • অন্যথায়,

      • ঢাল :=(y2 - y1) /(x2 - x1)

      • ঢাল [ঢাল] :=1 + (ঢাল [ঢাল] যদি প্রস্থান হয় অন্যথায় 0)

  • যদি ঢাল খালি না হয়, তাহলে

    • res :=res এর সর্বোচ্চ এবং (একই + ঢালের সমস্ত মানের তালিকার সর্বোচ্চ)

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))

ইনপুট

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

আউটপুট

4