[Algorithm] CCW Algorithm [펌]

퍼온곳: https://www.acmicpc.net/blog/view/27

Counter Clock Wise

세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제: CCW

가능한 경우의 수는 총 3가지가 있습니다. 반시계 방향, 시계 방향, 일직선. 시계 방향을 -1, 일직선을 0, 반시계 방향을 1이라고 했을 때, P1은 검정색, P2는 초록색, P3을 파란색으로 나타내면 아래 그림과 같습니다.

세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구할 수 있습니다. $S$를 점 P1, P2, P3로 이루어진 삼각형의 면적이라고 했을 때

$$2\times S=\left|\begin{array}{ccc}{x}_1& y_1& 1\\ x_2& y_2& 1\\ x_3& y_3& 1\end{array}\right|=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)$$

입니다.

여기서 S의 부호에 따라서, 다음과 같이 세 가지로 나눌 수 있습니다.

• S > 0: 반시계 방향
• S = 0: 일직선
• S < 0: 시계 방향

코드로 나타내면 아래와 같습니다.

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } else if (temp < 0) {
        return -1;
    } else {
        return 0;
    }
}

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