[알고리즘 정리] CCW(Counter Clock Wise) 알고리즘

CCW는 3점을 이은 선분의 방향성에 대해서 찾는 방법이다.

찾는 방법은 삼각형의 넓이 구하는 공식을 이용한다.

공식은 생각보다 어렵지 않다.

2S의 절대값에 나누기 2를 한 값이 세점의 삼각형의 넓이가 된다.

여기서 세 점의 방향성을 알기위해 2S값을 주목한다.

P1이 파랑, p2 주황, P3 초록 일 때, 

시계방향이면 2S의 값이 +, 일직선이면 0, 반시계방향이면 - 값을 가지게 됩니다.

관련 문제 : 백준(BOJ) 2987 사과나무 **