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

ধরুন আমাদের একটি কোঅর্ডিনেটের তালিকা দেওয়া আছে। প্রতিটি কোঅর্ডিনেটে x এবং y মান থাকে যা কার্টেশিয়ান সমতলে একটি বিন্দু নির্দেশ করে। এখন সবচেয়ে বেশি কতগুলো বিন্দু একটি সরল রেখায় পড়ে তা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট coordinates = [[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
• প্রতিটি i (0 থেকে len(points)-1) এর জন্য:
  • (x1, y1) := points[i]
  • slopes := {} (ঢাল গণনার জন্য মানচিত্র)
  • same := 1 (একই বিন্দুর সংখ্যা)
  • প্রতিটি j (i+1 থেকে শেষ) এর জন্য:
    • (x2, y2) := points[j]
    • যদি x2 == x1, তবে slopes[inf] += 1
    • অন্যথায় যদি x1 == x2 and y1 == y2, তবে same += 1
    • অন্যথায়, slope = (y2 - y1) / (x2 - x1) এবং slopes[slope] += 1
  • যদি slopes খালি না হয়, তবে res = max(res, same + max(slopes.values()))
• 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