A Common Programmer

퍼온곳: 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로 이루어진 삼각형의 면적이라고 했을 때

입니다.

여기서 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

https://www.acmicpc.net/blog/view/27

위 자료를 참고하면 CCW 알고리즘에 대해 자세히 설명되어 있다.

간단히 설명하면 CCW 알고리즘은 점 3개의 방향이 시계방향인지 반시계방향인지 일직선인지를 판단하는 알고리즘이다.

그래서 CCW는 세 점으로 이루어진 삼각형의 면적을 통해서 판단한다.

넓이가 0보다 크면 반시계방향,

넓이가 0보다 작으면 시계방향,

넓이가 0이면 일직선

방법은 첫번째 점부터 (x1, y1)으로 두고 벡터의 외적을 통해 넓이를 구한다.

필자는 빨리 풀려고 직관적으로 풀었으나 point라는 자료형을 사용하면 좀더 깔끔해진다.

<Segment Tree>

https://www.acmicpc.net/blog/view/9

<Fenwick Tree>

http://www.crocus.co.kr/666

https://www.acmicpc.net/blog/view/21