Giả sử ta có một danh sách các điểm trên mặt phẳng. Ta cần tìm diện tích tam giác lớn nhất có thể tạo thành bởi bất kỳ 3 điểm nào trong số đó.
Ví dụ, nếu đầu vào là [[0,0],[0,1],[1,0],[0,2],[2,0]], thì đầu ra sẽ là 2
Để giải quyết, ta thực hiện các bước sau:
- res := 0
- N := kích thước danh sách points
- Với i từ 0 đến N - 2, thực hiện:
- Với j từ i + 1 đến N - 1, thực hiện:
- Với k từ i + 2 đến N, thực hiện:
- (x1, y1) := points[i],
- (x2, y2) := points[j],
- (x3, y3) := points[k]
- res := max của res, 0.5 * |x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2)|
- Với k từ i + 2 đến N, thực hiện:
- Với j từ i + 1 đến N - 1, thực hiện:
- Trả về res
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
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(i + 2, N): (x1, y1), (x2, y2), (x3, y3) = points[i], points[j], points[k] res = max(res, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))) return res ob = Solution() print(ob.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]))
Đầu vào
[[0,0],[0,1],[1,0],[0,2],[2,0]]
Đầu ra
2.0