CCW(Counter ClockWise)

CCW 알고리즘

CCW 알고리즘은 Counter ClockWise의 약자로, 세 점의 방향성을 판단하는데 사용된다. 세 점

가 주어졌을 때 이 점들이 시계 방향인지, 반시계 방향인지, 아니면 일직선 상에 있는지를 판별한다.

수학적 원리

세 점의 방향은 벡터의 외적을 이용해서 구할 수 있다.

벡터 AB = (x₂-x₁, y₂-y₁)
벡터 AC = (x₃-x₁, y₃-y₁)
외적값
CCW = (x₂-x₁) * (y₃-y₁) - (y₂-y₁) * (x₃-x₁)
→ 위 식은 사실 AB와 AC가 만드는 평행사변형의 부호있는 면적 * 2이다.

결과 해석

CCW > 0 → 반시계 방향
CCW < 0 → 시계 방향
CCW = 0 → 세 점이 일직선 상에 있음

c++

#include <iostream>
using namespace std;

struct Point {
    long long x, y;
};

int ccw(Point a, Point b, Point c) {
    long long result = (b.x - a.x) * (c.y - a.y) - 
                       (b.y - a.y) * (c.x - a.x);

    if (result > 0) return 1;   // 반시계 방향
    if (result < 0) return -1;  // 시계 방향
    return 0;                   // 일직선
}

int main() {
    Point a, b, c;
    cin >> a.x >> a.y;
    cin >> b.x >> b.y;
    cin >> c.x >> c.y;

    int res = ccw(a, b, c);
    cout << res << "\n"; // 1, -1, 0 출력
}

활용 예시

백준에서는 주로 선분 교차 여부를 판단하는 과정에 사용한다. 또한 다각형의 넓이를 계산하는 과정에도 사용된다.