2D 평면의 단순한 다각형 끝점을 나타내는 정렬된 점 목록이 있다고 가정합니다. 이 다각형의 면적을 찾아야 합니다.
따라서 입력이 점 =[(0, 0), (0,5), (3, 5), (3,0)]과 같으면 출력은 15가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- getInfo() 함수를 정의합니다. x1, y1, x2, y2가 필요합니다.
- 반환 x1*y2 - y1*x2
- 메인 방법에서 다음을 수행합니다.
- N :=포인트 크기
- (첫 번째, 첫 번째) :=포인트[0]
- (prevx, prevy) :=(firstx, firsty)
- res :=0
- 1~N-1 범위의 i에 대해 다음을 수행합니다.
- (nextx, nexty) :=포인트[i]
- res :=res + getInfo(prevx, prevy, nextx, nexty)
- prevx :=nextx
- prevy :=다음
- res :=res + getInfo(prevx, prevy, firstx, firsty)
- 반환 |res| / 2.0
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def getInfo(x1, y1, x2, y2): return x1*y2 - y1*x2 def solve(points): N = len(points) firstx, firsty = points[0] prevx, prevy = firstx, firsty res = 0 for i in range(1, N): nextx, nexty = points[i] res = res + getInfo(prevx,prevy,nextx,nexty) prevx = nextx prevy = nexty res = res + getInfo(prevx,prevy,firstx,firsty) return abs(res)/2.0 points = [(0, 0), (0,5), (3, 5), (3,0)] print(solve(points))
입력
[(0, 0), (0,5), (3, 5), (3,0)]
출력
15.0