[Python] 백준 11758 - CCW

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

 

문제

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

---

 

풀이

CCW 알고리즘은 주어진 세 점의 방향성을 판별하는 매우매우 유명한 알고리즘이다. 오늘은 이 알고리즘을 직접 유도해보자.

이 알고리즘의 핵심 아이디어는 바로 벡터의 외적이다.

그림과 함께 살펴보자.

 

주어진 점 P1, P2, P3가 있고 이것이 순서대로 반시계 방향을 이룬다고 해보자.

 

P1P2 벡터와 P2P3 벡터의 외적을 생각해보자. 반시계 방향일 경우 두 벡터의 외적은 종이를 뚫고 나오는 방향, 즉 +z 방향이다.

 

 

반대로 시계 방향이면 외적값은 종이를 뚫고 들어가는 방향, 즉 -z 방향이 되게 된다.

 

 

만약 세 점이 일직선이어서 벡터들끼리 평행한 경우는 외적이 0이라고 할 수 있다.

 

외적을 두 벡터가 만드는 평행사변형의 넓이라고 생각하면 쉽다. 일직선이면 평행사변형이 만들어지지도 않으니 넓이는 0일 것이다.

 

 

이제 세 점의 좌표를 잡고 외적 공식을 이용해보자.

 

 

그림에서 표시된 1번 벡터와 2번 벡터는 다음과 같이 나타낼 수 있을 것이다.

 

외적은 3차원 계산이기때문에 임의로 z축 성분을 0이라고 잡고 계산하면

 

 

 

조금 긴 식을 얻을 수 있다.

 

밑줄친 부분이 +z 방향을 나타내니, 이 값이 양수면 CCW, 음수면 CW, 0이면 일직선이 될 것이다.

 

이를 코드로 나타내고 제출하면 쉽게 AC를 얻을 수 있다.

 

이 CCW 알고리즘은 앞으로 풀 모든 기하 문제의 기반이 되니, 공식은 외워두는 것이 좋겠다.

 

#아이디어: 외적은 CCW!

x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())

tmp = (x2-x1)*(y3-y2) - (x3-x2)*(y2-y1)

if tmp > 0:
    print(1)
elif tmp < 0:
    print(-1)
else:
    print(0)