ได้รับรายการจุดบนระนาบ 2 มิติ ต้องการหาพื้นที่ของสามเหลี่ยมที่ใหญ่ที่สุดที่สามารถสร้างได้จากจุดใด ๆ 3 จุด
ตัวอย่าง
points = [[0,0],[0,1],[1,0],[0,2],[2,0]] → พื้นที่มากที่สุด = 2.0
ขั้นตอนการแก้ปัญหา
- ใช้สูตรพื้นที่สามเหลี่ยมจากพิกัด 3 จุด:
Area = 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|
- วนทุกชุดของ 3 จุด (Triple nested loop)
- คำนวณพื้นที่ เก็บค่าสูงสุด
- คืนค่าพื้นที่สูงสุด
การติดตั้งใน Python
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
อินพุต / เอาต์พุต
Input: [[0,0],[0,1],[1,0],[0,2],[2,0]] Output: 2.0
