[알고리즘] CCW

구현 방식

• 외적을 통해 쉽게 구할 수 있다.
• 외적(v1, v2)의 결과값은 벡터 v1 과 v2 모두에 직교하는 벡터를 내놓는다.
• 그리고 왼손 엄지 법칙에 의해 반/시계 방향에 따라 벡터의 방향이 달라진다. 아래의 그림을 참고한다.

• 주어진 두 점은 2차원이지만,,! 3차원으로 생각해보면..! 벡터의 방향은 Z 값에 의해 결정되므로 Z 값을 비교해서 결과를 출력한다.

코드

• 최종 코드는 아래와 같다.

struct Vector
{
	Vector(int x, int y, int z)
	{
		X = x;
		Y = y;
		Z = z;
	}
	int X;
	int Y;
	int Z;
};

int main()
{
	pair<int, int> p1, p2, p3;
	cin >> p1.first >> p1.second;
	cin >> p2.first >> p2.second;
	cin >> p3.first >> p3.second;

	Vector v1 = Vector(p2.first - p1.first, p2.second - p1.second, 0);
	Vector v2 = Vector(p2.first - p3.first, p2.second - p3.second, 0);

	solution(v1, v2);
}


void solution(Vector v1, Vector v2)
{
	Vector result = crossProduct(v1, v2);
	if (result.Z > 0) cout << -1;
	else if (result.Z < 0) cout << 1;
	else cout << 0;
}

Vector crossProduct(Vector v1, Vector v2)
{
	return Vector(
		v1.Y * v2.Z - v2.Y * v1.Z,
		v1.Z * v2.X - v2.Z * v1.X,
		v1.X * v2.Y - v2.X * v1.Y
	);

}