[CCW 알고리즘] 세 점으로 이루어진 선분의 방향성

2차원 좌표평면에 세 점 $p_1, p_2, p_3$가 주어질 때, 다음 식을 통해 $p_1 \to p_2 \to p_3$로 형성되는 선분의 방향성을 알 수 있다.

벡터의 외적 $S = (x_1y_2 + x_2y_3 + x_3y_1) - (x_2y_1 + x_3y_2 + x_1y_3)$

$if $   $ S < 0$, 시계방향

$if $   $ S = 0$, 일직선

$if $   $ S > 0$, 반시계방향

int CCW(pair<int,int> A, pair<int, int> B, pair<int, int> C) {
	int a = A.first * B.second + B.first * C.second + C.first * A.second;
	int b = B.first * A.second + C.first * B.second + A.first * C.second;
	if (a > b) return 1;
	else if (a == b) return 0;
	else return -1;
}