ম্যাক্স পয়েন্টস অন অ্যা লাইন সমস্যা
একটি ২D প্লেনে কিছু পয়েন্ট দেওয়া আছে। একই সরল রেখায় থাকা সর্বোচ্চ কতগুলো পয়েন্ট আছে তা বের করতে হবে।
উদাহরণ: পয়েন্টগুলো [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] → সর্বোচ্চ ৪টি পয়েন্ট একই রেখায়।
সমাধানের পদ্ধতি (O(n²) ব্রুট ফোর্স বালিশ স্লোপ তুলনা)
n < 3হলেnফেরত দিন- প্রতিটি পয়েন্ট জোড়া
(i-1, i)এর জন্য স্লোপ গণনা করুন - যদি দুটি পয়েন্ট একই হয়, সেই পয়েন্টের ফ্রিকোয়েন্সি কাউন্ট করুন
- অন্যথায়, সব পয়েন্টের সাথে স্লোপ মিলিয়ে কাউন্ট করুন:
(y3-y2)*(x2-x1) == (y2-y1)*(x3-x2)(ক্রস মাল্টিপ্লিকেশন দিয়ে ফ্লোট এড়ানো) - সর্বোচ্চ কাউন্ট আপডেট করুন
দ্রষ্টব্য: এটি O(n³) সমাধান। অপ্টিমাইজড O(n² log n) সমাধান হ্যাশম্যাপ স্লোপ কাউন্টিং দিয়ে সম্ভব।
C++ কোড উদাহরণ
[{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]
আউটপুট
4
