백준 2166번 다각형의 면적

링크텍스트 알고리즘 외적(cross product)을 이용하여 풀 수 있는 문제다. 점이 순서대로 주어지므로, 연속되는 두 점에 대한 외적값의 절반을 모두 더하면 된다. 시간복잡도 점의 개수를 n이라 할 때, 시간복잡도는 O(n)이다. 응용 외적은 이외에도 CCW 등에 사용된다. CCW(counter clockwise)는 어떤 점이 벡터에 대해 반시계 방향에 있다는 것을 의미한다. 즉, 벡터와 벡터의 시작점-목표점 간의 외적값이 양수면 counter clockwise, 음수면 clockwise이다. 한 점이 convex polygon(볼록 다각형)의 내부/외부에 있는지 판별할 때에도 사용할 수 있다. 다각형의 모든 선분에 대해 점이 counter clockwise 방향에 있는지 확인하면 된다.

2023년 1월 19일
·
0개의 댓글
·