ধরুন আমাদের কাছে স্থানাঙ্কের একটি তালিকা আছে। প্রতিটি স্থানাঙ্কের দুটি মান 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