[백준/Python] 11758번 CCW

문제

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

 

소스코드

p1 = list(map(int, input().split()))
p2 = list(map(int, input().split()))
p3 = list(map(int, input().split()))

def ccw(p1, p2, p3):
    return ((p2[0] - p1[0]) * (p3[1] - p2[1])) - ((p3[0] - p2[0]) * (p2[1] - p1[1]))
result = ccw(p1, p2, p3)
if result > 0:
    print(1)
elif result <0:
    print(-1)
else:
    print(0)

 

ccw를 세 점이 이루는 방향을 판단하는 데 사용합니다. 

점 a, b, c가 있을때 a -> b -> c의 ccw 알고리즘 결과가 양수라면 반시계방향, 음수라면 시계방향, 0이라면 직선상에 3점이 있는 것 입니다. 

 

ccw 알고리즘의 원리

ccw 알고리즘의 원리는 2개의 벡터 AB, BC의 외적을 구하는 것입니다. 

점 a, b, c를 각각 p1, p2, p3라고 하고 각 점에는 x, y 성분이 있다고 해보겠습니다. 

그렇다면 벡터 AB는 (p2.x - p1.x, p2.y - p1.y), 벡터 BC는 (p3.x - p2.x, p3.y - p2.y)입니다. 

 

벡터 외적 공식

여기까지 해보고 2개의 벡터의 외적을 구하는 공식은 아래와 같습니다. 

벡터 V1의 x, y성분을 (A, B), 벡터 V2의 성분을 (C, D)라고 한다면 

 이고 이것은 

외적 공식에 의해 A * D - B * C입니다. 

 

A * D - B * C에 벡터 AB (p2.x - p1.x, p2.y - p1.y), 벡터 BC (p3.x - p2.x, p3.y - p2.y) 을 대입한다면 ccw 값을 얻을 수 있습니다.