[백준 파이썬] 11758 CCW

📌문제 출처

백준 단계별 문제풀이 : 기하2
https://www.acmicpc.net/problem/11758

11758번: CCW

❓ 문제

📗 풀이 코드

'''
선분의 진행 방향이 어느 방향으로 바뀌었는지 확인하는 문제이다.
두 벡터의 외적을 구하는 공식을 활용한 CCW(counter clock wise) 알고리즘으로 풀 수 있다.

두 벡터의 외적의 크기는 두 벡터가 만드는 평행사변형의 넓이와 같고
방향은 두 벡터와 모두 수직하며, 사이각에 따라서 그 부호가 결정된다.
따라서 벡터의 부호에 따라서 두 선분이 이루는 방향을 구할 수 있다.
AxB = absin(angle)이라는 외적 공식을 활용하자.
'''
input = open('input.txt').readline

def solution():
    def ccw(s1,s2,s3): # 외적의 크기를 구하는 공식
        return (s1[0]*s2[1]+s2[0]*s3[1]+s3[0]*s1[1])-(s2[0]*s1[1]+s1[0]*s3[1]+s3[0]*s2[1])

    spots = [list(map(int, input().split())) for _ in range(3)] # 세 개의 점
    ex = ccw(*spots) # 외적 결과
    if ex > 0 : # 반시계 방향
        print(1)
    elif ex == 0 : # 일직선
        print(0)
    else : # 시계 방향
        print(-1)

if __name__ == '__main__':
    solution()

✍ 벡터 외적을 활용한 풀이 이해

두 벡터가 이루는 각에 따른 외적 벡터의 방향(부호)

세 점 a,b,c가 있을 때 선분 ab와 선분 bc가 이루는 각의 방향을 구하기 위해서 벡터 외적의 성질을 이용할 수 있다.

중심각(θ)을 세개의 점을 a,b,c 순으로 이었을때 생기는 각이라고 한다면 두 벡터의 외적 벡터의 크기는 삼각형 abc의 크기인 absin θ가 되고 그 방향은 위 그림처럼 오른손 법칙에 따라 반시계방향 각이면 +방향이, 시계방향 각이면 -방향이 된다.

삼차원 벡터의 행렬 연산

그런데 벡터의 외적은 신발끈 공식이라고 하는 삼차원 벡터의 행렬 연산으로 쉽게 구할 수 있다.

위와 같은 공식에서 문제에서 처럼 좌표평면에서의 세 점을 A(x1,y1,0), B(x2,y2,0), C(x3,y3,0)라고 했을 때,
Z축은 0으로 고정이기에 벡터 AB는 (x2-x1,y2-y1,0), 벡터 BC는 (x3-x2,y3-y2,0)가 된다.

따라서 외적의 크기는 위 그림에서 a1*b2-a2*b1이며 세 점의 좌표값을 직접 넣으면,

벡터 AB, 벡터 BC의 외적은(0,0,(x2-x1)(y3-y2)-(y2-y1)(x3-x2))이 되고 크기와 방향은 z축 원소와 같아진다.