[알고리즘] CCW(Counter ClockWise) 기하 알고리즘

1. 개요

1. 세 점의 방향관계를 알 수 있는 알고리즘

출처 : https://snowfleur.tistory.com/98

 

2. 외적

• http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/ 링크 참조
• 외적의 기하학적 표현

출처 : http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/

출처 : http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/

정리하자면)
1. 반시계방향이면 윗 방향인 (+) 값이 나온다.
2. 시계방향이면 아랫 방향인 (-) 값이 나온다.
3. 동일한 방향이면 0 값이 나온다.

• 계산식은 아래와 같다.
• https://snowfleur.tistory.com/98 참조

출처 : https://snowfleur.tistory.com/98

출처 :  https://snowfleur.tistory.com/98

출처 : https://snowfleur.tistory.com/98

 

3. 소스 코드

// CCW(Counter ClockWise) 알고리즘
int ccw(pair<long long, long long> p1, pair<long long, long long> p2, pair<long long, long long> p3)
{
	// 외적 계산
	long long temp = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
	temp -= p1.second * p2.first + p2.second * p3.first + p3.second * p1.first;

	if (temp > 0) return 1;			// 반시계 방향
	else if (temp == 0) return 0;	// 일직선
	else return -1;					// 시계 방향
}

 

4. 문제

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