CCW

개요

오늘은 CCW 알고리즘을 소개하려고 한다. 정말 정말 간단한 알고리즘이라서 길게 설명할 필요도 없다. 바로 시작하자.

CCW?

일단 CCW가 뭘까?

CCW는 counter clockwise라는 뜻이다. 흠... 무슨 말인지 잘 이해가 되지 않을 수도 있다. 간단하게 설명하자면 점 사이의 위치 관계를 알아내는 알고리즘이다. 좀 더 자세히 알아보자.

평면 위에 점 3개가 있다. 각각 A, B, C이다. 이때 직선 AB에 의해 평면은 두 부분으로 나뉜다. CCW는 이 상황에서 점 C가 두 부분 중 어느 곳에 있는지 알려준다.

이렇게 생각해보자. 자동차로 A, B, C를 순서대로 방문할 것이다. 그런 B에서 좌회전을 해야하는지 (counter clockwise), 우회전을 해야 하는지(clockwise) 알려주는 알고리즘이다. 또는 그대로 직진 할 수 도 물론 있다.

이제 작동 원리를 알아보자. 간단하다. (맨날 간단하다고만 한다....) 바로 벡터를 이용하는 것이다. 그중에서도 벡터의 외적을 이용할 것이다. (급 수학)

벡터 AB를 \(\vec x\), BC를 \(\vec y\)라고 하자. 이때 반시계 방향일 때 \(\vec x \times \vec y\)와 시계방향일때의 방향이 반대, 즉 부호가 서로 다를 것이다. 이것을 수식화 하여 구현한 것이 바로 CCW이다.

이제 좀 더 자세하게 가보자.

\(\vec x = (a,b)\), \(\vec y = (c,d)\) 라고 하면 \(|\vec x \times \vec y| = |ad-bc|\)이고, 방향은 반시계의 경우 양수, 시계 방향이 음수가 나온다. 0인경우는 세 점이 한 직선 상에 있음을 말한다.

우와 설명이 끝났다. 바로 코드로 가보자.

코드

x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
x3,y3=map(int,input().split())
xx1=x2-x1
yy1=y2-y1
xx2=x3-x2
yy2=y3-y2
t=xx1*yy2-xx2*yy1
if t>0:
    print(1)
elif t==0:
    print(0)
else:
    print(-1)

위 코드는 백준 11758의 해법이다. 문제에서는 세 점이 어느 방향으로 배열되어 있는지 경우에 따라서 -1, 0, 1을 출력하라고 한다. 자세한 것은 직접 확인하자. (절대! 귀찮은 것이 아니다.)

11758번: CCW

Baekjoon Online Judge스타트링크 (Startlink)

확장

CCW 알고리즘은 매우 다양한 알고리즘으로 확장된다. 사실 기하학 알고리즘의 기본중 하나라고 할 수 있다.

볼록 껍질이나 선분 교차 판정, 신발끈 공식을 적용하기 위한 전 처리 등에 사용되는 만큼, 한 번 쯤 배워두면.... 좋다.