평면 상의 다각형의 넓이 구하는 신발끈 공식 구현

1. 문제

 

2166번: 다각형의 면적 (acmicpc.net)

2166번: 다각형의 면적

 

2. 풀이

 

2차원 평면상에 n개의 점으로 이루어진 다각형의 넓이를 구하는 방법으로 신발끈 공식이라고 있다

 

 

유도는 생략하고 그냥 그대로 구현해보자

 

2개의 x만 가지는 리스트와 y만 가지는 리스트를 구한다

 

x 리스트를 인덱스로 순회해서, 1칸 앞 인덱스의 y와 곱해서 합해주고

 

y리스트를 인덱스로 순회해서 1칸 앞 인덱스의 x와 곱해서 합해주고

 

두 결과를 빼서 절댓값을 취하면 될 것

 

from sys import stdin

n = int(stdin.readline())

pointX = []
pointY = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    pointX.append(x)
    pointY.append(y)


pointX.append(pointX[0])
pointY.append(pointY[0])

summation = 0

for i in range(n):
    
    summation += pointX[i]*pointY[i+1]
    summation -= pointY[i]*pointX[i+1]

print(f"{abs(summation)/2:.1f}")

 

 

이 문제는 점이 다각형을 이루는 순서대로 주어져서 공식이 성립하는데

 

점이 순서대로 이루어지지 않으면 다각형이 유일하게 결정되지 않을 수 있고

 

또 다각형의 각 변이 교차하지 않아야 성립한다고 한다

 

 

 

신발끈 공식 - 나무위키 (namu.wiki)

신발끈 공식 - 나무위키