파이썬에서 가장 큰 삼각형 영역

평면에 점 목록이 있다고 가정합니다. 세 점으로 만들 수 있는 가장 큰 삼각형의 면적을 찾아야 합니다.

따라서 입력이 [[0,0],[0,1],[1,0],[0,2],[2,0]]과 같으면 출력은 2

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• res :=0
• N :=포인트 목록의 크기
• 0 ~ N - 2 범위의 i에 대해
  • i + 1 ~ N - 1 범위의 j에 대해
    • i + 2 ~ N 범위의 k에 대해
      • (x1, y1) :=포인트[i],
      • (x2, y2) :=포인트[j],
      • (x3, y3) :=포인트[k]
      • res :=최대 res, 0.5 * |x1 *(y2 - y3) + x2 *(y3 - y1) + x3 *(y1 - y2)
• 반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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]]))

입력

[[0,0],[0,1],[1,0],[0,2],[2,0]]

출력

2.0