[백준] 2166. 다각형의 면적 - 파이썬

https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

 

풀이

vector의 외적(Cross Product)을 통한 삼각형의 넓이를 구하는 방법을 이용해 풀었다.

첫 번째 입력되는 점을 기준으로 잡고,

[dot1, dot2, dot3 triangle] => (dot2-dot1) vector, (dot3-dot1) vector's cross product

[dot1, dot3, dot4 triangle] => (dot3-dot1) vector, (dot4-dot1) vector's cross product

...

 

와 같이 계산 후, 모든 삼각형의 면적값을 더한 뒤, 마지막에 절댓값 계산만 넣어주면 된다.

외적을 이용한 계산이기 때문에, 오목점이 있는 다각형이라도, 자동으로 전체 면적에서 마이너스 된다.

 

N = int(input())

dots = []
for _ in range(N):
    dots.append(list(map(float, input().split())))

area = 0

'''triangle: 1st dot, and ith, (i+1)th dot.'''
for i in range(1, len(dots)-1):
    a = dots[0]
    b = dots[i]
    c = dots[i+1]

    '''vector 1 : (x2-x1, y2-y1)'''
    vec1 = [b[0]-a[0], b[1]-a[1]]
    '''vector 2 : (x3-x2, y3-y1)'''
    vec2 = [c[0]-a[0], c[1]-a[1]]

    '''add triangle's area to total area'''
    area += (vec1[0]*vec2[1] - vec1[1]*vec2[0])/2

print(abs(area))