CCW

세 점의 회전 방향을 확인하는 방법으로 CCW(Counter-ClockWise)를 사용할 수 있다.
기준점 A에서 점 B를 거쳐 점 C로 향하는 방향이 시계 반대방향이면 양수,
시계 방향이면 음수, 일직선이면 0이 나온다.

코드로 나타내면 다음과 같다.

typedef long long ll;

// Point 구조체 정의
struct Point {
	int x;
    int y;
    
    Point operator-(Point other) {
    	Point ret;
        
        ret.x = this->x - other.x;
        ret.y = this->y - other.y;
        
        return ret;
    }
}

ll ccw(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

ll ccw(Point base, Point a, Point b) {
	return ccw(a - base, b - base);
}

// 방향 판단 함수
int direction(Point base, Point a, Point b) {
	ll res = ccw(base, a, b);
    
    if(res > 0) return 1;			// 시계 반대방향
    else if(res < 0) return -1;		// 시계 방향
    else return 0;					// 일직선
}