삼각형의 면적 구하기, 백준 2166 다각형의 면적

삼각형의 면적을 구하는 방법 중 하나인 삼각형을 이루는 두 변(벡터)을 활용하는 것이다.

참조:

https://math.oregonstate.edu/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/crossprod/crossprod.html

간략히 말하면 

벡터 a, b 가 이루는 삼각형의 너비는 |a| * |b| * sin (<ab)  * 1/2 인데,  |a|를 밑변이라했을때 |b| *sin (<ab)가 높이와 같다.

따라서 밑변 (|a|) * h * 1/2 이다. 즉, 삼각형의 너비 공식과 같다.

이 때, 두 벡터 a, b를 외적(cross product) 한 것은 삼각형의 너비 *2 와 같다. 

| a x b | = |a|*|b| * sin(<ab) 이다. 

그러므로, 1/2 * | a x b | = 삼각형의 너비다.

2 차원인 두 벡터의 외적은 간단하다. ( ax,by ) x ( cx, dy ) = (ad - bc)

백준에서 삼각형 너비를 구하는 문제는 없지만,

다각형의 너비를 구하는 문제는 있다.

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

재밌다. 문제풀 때 엄청 틀렸었다.

일단 왜 틀렸냐면, 다각형이 말그대로 `다 각 형`이기때문에, 구부러진 형태도 있다는 것을 생각 하지 못하고

항상 매번 구하는 삼각형의 너비를 절대값을 취해줬었기 때문이다.

구부러진 형태의 것에서는 어떤 삼각형은 이전 삼각형 너비에서 빼주는 모양을 띄는 것을 간과하고 있었던 것이다.

정답 소스보러가기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/2166.cc