[Algorithm] CCW 알고리즘

 

CCW(Counter Clock Wise) 알고리즘은

• 벡터의 외적을 통해 세 점의 위치 관계가 시계방향인지 아닌지 판별하는 알고리즘이다.

 

선분 교차 판별

• ccw 알고리즘을 이용하여 선분 교차를 판별할 수 있다.
• 한 선분을 기준으로 같은 방향에 위치할 경우 선분은 교차되지 않고 그렇지 않은 경우 교차한다.

즉, ccw 함수의 수행 결과로 반시계 방향이 1, 시계 방향의 -1을 갖는다면 CCW(A, B, C)의 결과와 CCW(A, B, D) 결과의 곱이 -1 이 되는 경우 서로 다른 방향에 위치하게 된다.

다만, 아래와 같이 다른 방향이어도 교차하지 않는 경우가 있다.

 

• 이 경우는 선분 CD 에 대해서도 CCW 알고리즘을 수행하여 판별한다.
• 또한, 평행인 경우도 존재하므로, 조건을 잘 분기해주어야 한다.

• 신발끈 공식을 이용하여 풀어줄 수 있다.

 

참고문제 

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

11758번: CCW

 

 

dot = []
for i in range(3):
    dot.append(list(map(int, input().split())))

def ccw(p1, p2, p3):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    return (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)

result = ccw(dot[0], dot[1], dot[2])
if result > 0:
    print(1)
elif result < 0:
    print(-1)
else:
    print(0)