[BOJ 2166] 다각형의 면적
- 문제풀이
문제
2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.
출력
첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
문제 조건이 다각형이다. 근데 이게 전체적으로 볼록한지, 아니면 오목한 부분이 있는지는 모른다. 그래서 그냥 빙 돌아가면서 전체 넓이를 계산하는 것은 불가능하다.
그러면 취할 수 있는 방법이 하나 있다. 다각형은 여러개의 삼각형으로 쪼갤 수 있다는 것. 한 점을 기준으로 다른 점들에 모두 선을 그으면 모든 넓이를 담을 수 있는 여러 삼각형들이 만들어진다. 이 삼각형들의 넓이를 모두 더하면 최종 다각형의 넓이가 나오게 된다. 그럼, 삼각형들의 넓이만 구해낼 수 있으면 전체 다각형의 넓이를 구할 수 있게 된다.
삼각형의 넓이는 사선공식을 이용하면 된다. 신발끈 공식이라고도 하는데, 세 점 $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$에 대해서 삼각형의 넓이 $S$는 아래와 같이 계산할 수 있다.
\[S = \frac{1}{2} \begin{vmatrix} x_1 & x_2 & x_3 & x_1 \\ y_1 & y_2 & y_3 & y_1 \\ \end{vmatrix} = \frac{1}{2} = \lvert (x_1 y_2 + x_2 y_3 + x_3 y_1) - (x_2 y_1 + x_3 y_2 + x_1 y_3) \rvert\]이 값을 구하는 방법으로는 CCW 알고리즘을 이용한다. 잠깐 생각해보면 알겠지만, 절댓값으로 둘러싸인 부분이 CCW 알고리즘의 결과와 같다는 것을 알 수 있다. CCW는 두 벡터의 외적을 하는데, 외적의 결과값이 두 벡터로 만들 수 있는 평행사변형의 넓이와 같기 때문이다. 해서 CCW 알고리즘의 결과값을 반으로 나누면 삼각형의 넓이를 구할 수 있다. 이 값들을 모두 더하면 전체 다각형의 넓이를 구할 수 있다.
다각형이 볼록하지 않은 부분에 대해서는 어떻게 하냐고 생각할 수 있는데, 오목한 부분에 대해서는 CCW값이 반대 부호로 나온다. 실제로 삼각형을 그려보다보면 오목한 부분에서는 겹치는 부분이 있는데, 그것들의 처리도 CCW가 알아서 해준다는 느낌.
소스코드
Github Link : Source Code
참고 알고리즘 : CCW 알고리즘