[BOJ/백준] 2166 : 다각형의 면적

문제 링크
백준 2166 : 다각형의 면적

문제

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

출력

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

---

아이디어

문제를 보자마자 고등학교 시절에 배웠던 좌표를 사용하여 다각형 넓이를 구하는 과정이 생각났었다.
그 수식 한 번만 사용하면 되는 쉬운 문제이지만 수식을 함께 정리하고 싶어서 기록을 남긴다.

N각형 넓이 계산 방법

(x1, y1), (x2, y2), ..., (xn, yn)으로 표현되는 2차원 평면상의 n각형이 주어졌을 때, 이 n각형의 넓이를 구하기 위해서는 다음 수식을 적용하면 된다.
(이때 주어진 좌표의 순서는 시계, 또는 반시계방향으로 연결된 형태를 가정했을 때의 순서로 주어져야한다.)

$$
S = \frac{1}{2}\left( \left| \begin{matrix} x_1 & x_2 \ y_1 & y_2 \end{matrix}\right| + \left| \begin{matrix} x_2 & x_3 \ y_2 & y_3 \end{matrix}\right| + \cdots +\left| \begin{matrix} x_n & x_1 \ y_n & y_1 \end{matrix}\right| \right)
$$

$$
S = \frac{1}{2}\left( x_1y_2 - x_2y_1 + x_2y_3-x_3y_2 + \cdots + x_ny_1 - x_1y_n\right)
$$

더 자세한 설명이나 증명은 이 블로그를 참고하면 좋을 것 같다. 나중에 시간이 나면 더 자세히 조사해서 증명과정을 블로그에 포스팅 할 예정이다.

알고리즘 : 코드

import sys

input = sys.stdin.readline
N = int(input())
coordinate = [list(map(int, input().split())) for _ in range(N)]
coordinate.append(coordinate[0])
area = 0
for i in range(N):
    area += coordinate[i][0] * coordinate[i + 1][1]
    area -= coordinate[i + 1][0] * coordinate[i][1]
result = round(area / 2, 1)
print(max(result, -1 * result))

회고

기하학 오랜만에 만나니까 재밌다.