[알고리즘] 벡터의 외적

벡터란 크기와 방향을 가지는 물리량이다. 

길이와 방향성을 지니는 선분이라 생각하면 된다. 

 

벡터의 외적 구하기

외적은 두 벡터에 대해 수직인 벡터를 구하는 연산이다. 

pair<int, int> x = make_pair(2, 5);
pair<int, int> y = make_pair(4, -2);

int tmp = x.first * y.second - x.second * y.first;

 

CCW 알고리즘

벡터의 외적을 응용한 알고리즘이다. 

세 점이 주어졌을 때, 외적의 부호를 판단하여 세 점의 방향성을 확인할 수 있다.

점 A를 기준으로 세 점의 방향성을 구해보자. 

두 벡터 AB 와 AC의 외적의 부호를 통하여 이를 결정할 수 있다. 

세 점을 A(x1, y1), B(x2, y2), C(x3, y3) 라 하면

두 벡터는 (x2- x1, y2 - y1), (x3 - x1, y3 - y1) 이라 할 수 있다. 

이를 외적 공식에 대입하면

(x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

으로 표현할 수 있다. 

 

이때 그 값이 음수일 경우 세 점은 시계 방향, 양수일 경우는 반시계 방향이다. 

long long ccw(pair<long long, long long>p1, pair<long long, long long>p2, pair<long long, long long>p3) {
	long long s = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
	s -= (p1.second * p2.first + p2.second * p3.first + p3.second * p1.first);

	if (s > 0) return 1;
	else if (s == 0) return 0;
	else return -1;
}

 

코드는 다음과 같이 표현할 수 있다.