সমস্যা বিবরণ
একটি প্লেনে কিছু পয়েন্ট দেওয়া থাকে। যেকোনো ৩টি পয়েন্ট দিয়ে তৈরি ত্রিভুজের মধ্যে সর্বোচ্চ এলিয়া বের করুন।
উদাহরণ
ইনপুট: [[0,0],[0,1],[1,0],[0,2],[2,0]] → আউটপুট: 2.0
গাণিতিক সূত্র
ত্রিভুজের শীর্ষবিন্দু (x1,y1), (x2,y2), (x3,y3) হলে এলিয়া = 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|
এলগরিদম
res = 0,N = len(points)।- ৩টি নেস্টেড লুপ দিয়ে সব সম্ভাব্য ত্রিকোণ (i, j, k) চেক করুন।
- প্রতিটি ত্রিকোণের জন্য উপরের সূত্রে এলিয়া হিসাব করুন এবং
res = max(res, area)আপডেট করুন। resরিটার্ন করুন।
সময় জটিলতা: O(N³) — ছোট ইনপুটের জন্য উপযোগী।
পাইথন বাস্তবায়ন
class Solution:
def largestTriangleArea(self, points):
res = 0
N = len(points)
for i in range(N - 2):
for j in range(i + 1, N - 1):
for k in range(j + 1, N):
(x1, y1), (x2, y2), (x3, y3) = points[i], points[j], points[k]
area = 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
res = max(res, area)
return res
ob = Solution()
print(ob.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]])) # 2.0ইনপুট / আউটপুট
ইনপুট: [[0,0],[0,1],[1,0],[0,2],[2,0]] আউটপুট: 2.0
