[BOJ] 2166 - 다각형의 면적

 

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

 

* 신발끈 공식으로도 풀 수 있고, 사실 오목다각형이어도 성립한다고 하나, 오목다각형에서는 안 되는 줄 알고 다른 풀이를 썼다.

적분에서 아이디어를 얻어 사용한 풀이입니다. 다각형의 좌표가 순서대로 돌아갑니다. 만일, x좌표의 값이 증가하면 넓이가 증가하게 잡았고, x좌표가 줄어드는 방향에서는 넓이를 뺍니다.  즉,  x축에서 진행하는 변이 이루는 사다리꼴의 넓이의 증감을 고려합니다.  이를 위해서 , 평행이동까지 진행합니다.

N = int(input())
area = 0
point_list = []
y_list = []
for i in range(0, N):
    cur_x, cur_y = map(int, input().split())
    point_list.append([cur_x, cur_y])
    y_list.append(cur_y)
# 적분 아이디어를 쓰기 위해, y축을 0위로 돌려야 한다.
# 최솟값을 모두 다 빼버리자. 평행이동을 써야 한다.
y_min = min(y_list)

for i in range(0, N):
    point_list[i][1] -= y_min

for i in range(0, N):
    if i < N-1:
        cur_x, cur_y = point_list[i]
        next_x, next_y = point_list[i+1]
    else:
        cur_x, cur_y = point_list[N-1]
        next_x, next_y = point_list[0]
        
    # 양의 방향으로 넓이를 적분한다.
    if cur_x < next_x:
        area += (1/2) * (next_x - cur_x) * (cur_y + next_y)
    # 음의 방향으로 넓이를 적분한다.
    elif cur_x > next_x:
        area -= (1/2) * (cur_x - next_x) * (cur_y + next_y)
print(abs(area))