[백준 BOJ] 11758 CCW (python)

문제 링크 : https://www.acmicpc.net/problem/11758

11758번: CCW

최근까지 기하학 문제를 풀고 싶어 선분 교차라는 시리즈의 문제를 풀었습니다.

그러던 중 CCW라는 기하 알고리즘을 거의 필수적으로 사용해야하는 것을 알았기에 이 문제를 우선 풀게 되었습니다.

선분 교차 문제들은 내일부터 하나씩 풀이를 하기로 하고 오늘은 우선 알아야 할 CCW란 문제를 풀이하겠습니다.

 

CCW

CCW란 Counter Clock Wise의 줄임말로 P1, P2, P3라는 세 점이 있을 때 P1에서 P2를 지나쳐 P3로 갈때 방향을 시계 방향으로 꺾는지, 반시계 방향으로 꺾는지, 아니면 일직선을 이루는지를 판별하는 알고리즘입니다.

정말 기하에만 사용되는 알고리즘이라 실제 현업 코딩테스트에서는 잘 사용하지 않을 것 같습니다.

 

외적

CCW를 위해서는 외적을 이해할 필요가 있습니다.

선형대수에서의 행렬 outer product가 아니라 3차원 벡터에서의 cross product입니다.

x×y=(x2​y3​−x3​y2​,x3​y1​−x1​y3​,x1​y2​−x2​y1​)

다음과 같이 정의가 되며 이 알고리즘에서는 2차원 평면의 두 벡터에 대해 계산되므로 x3과 y3은 0으로 보아도 됩니다.

외적은 두 벡터와 수직되므로 1, 2번째 값은 0이 되고, 3번쨰 값, 즉, x1y2-x2y1이 저희가 관심을 가져야할 값이 됩니다.

x가 P1에서 P2로 가는 벡터, y가 P2에서 P3으로 가는 벡터라고 했을때 x1y2-x2y1은 반시계 방향이라면 양수, 시계 방향으라면 음수, 일직선이면 0이 됩니다.

문제에서는 1, -1, 0을 출력해야하므로 0이 아닌 경우 절댓값으로 나누어 준 후 출력해줍니다.

 

p1_x, p1_y = map(int, input().split())
p2_x, p2_y = map(int, input().split())
p3_x, p3_y = map(int, input().split())
ccw = (p2_x-p1_x)*(p3_y-p2_y)-(p3_x-p2_x)*(p2_y-p1_y)
if ccw:
    ccw //= abs(ccw)
print(ccw)