BOJ 11758 - CCW (Python3)

방법론만 알고 있으면 난이도가 미친 듯이 하락하는 몇몇 문제가 있다.

그 대표격인 예시로 아마 이 블로그 닫을 때까지 우려먹을 11402번 문제가 있고, 그리고 이 문제가 그러하다.

분명히 교과과정 외의 문제라 골드 V 지정에는 이견이 없지만, 그럼에도 불구하고 구현 난이도는 실버급이라고 생각한다.

자신이 있으면 직접 해 보자. 힌트는 벡터곱이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

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

 

입력

첫째 줄에 P₁의 (x₁, y₁), 둘째 줄에 P₂의 (x₂, y₂), 셋째 줄에 P₃의 (x₃, y₃)가 주어진다. (-10,000 ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 10,000) 모든 좌표는 정수이다. P₁, P₂, P₃의 좌표는 서로 다르다.

 

예제 입력)

# 예제 입력 1
1 1
5 5
7 3

# 예제 입력 2
1 1
3 3
5 5

# 예제 입력 3
1 1
7 3
5 5

 

출력

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

 

예제 출력)

# 예제 출력 1
-1

# 예제 출력 2
0

# 예제 출력 3
1

 

---

내 코드

p1,p2,p3 = tuple(map(int, input().split())),tuple(map(int, input().split())),tuple(map(int, input().split()))
u,v = (p2[0]-p1[0],p2[1]-p1[1]),(p3[0]-p1[0],p3[1]-p1[1])
x = u[0]*v[1]-v[0]*u[1]
if x==0: print(0)
else:
    print(1 if x>0 else -1)

 

일단 두 벡터의 외적부터 짚고 넘어가지.

두 공간벡터 \(x=(x_1, x_2, x_3), y=(y_1, y_2, y_3)\)에 대해서, 두 벡터의 외적 \(x\times y\)는 다음과 같이 정의된다.

$$ x\times y=det \begin{pmatrix} i&j&k \\ x_1&x_2&x_3 \\ y_1&y_2&y_3 \end{pmatrix} = (x_2y_3-x_3y_2,x_3y_1-x_1y_3, x_1y_2-x_2y_1)$$

그러면 두 점 다 z좌표가 0인 경우, 그러니까 xy평면 상의 평면벡터일 경우 외적은 다음과 같은 환상적인 결과를 가지고 오게 된다.

$$ x\times y = (0, 0, x_1y_2-x_2y_1) = (x_1y_2-x_2y_1)k $$

그리고 외적의 정의만 알게 된다면, CCW 문제는 끝이다!

 

평면에선, 각을 반시계로 잰다. 이건 고등학교 때 삼각함수를 배우며 주입이 되었을 것이다.

어떤 각을 측정할 때 동경은 x축의 양의 방향에서 시작하여 반시계 방향으로 돌고 blah blah...

그러므로 P₁, P₂, P₃가 반시계로 있다는 것은 선분 P₁P₂와 P₁P₃이 양의 각을 이루고 있다는 것이고, 시계방향으로 있다는 것은 선분 P₁P₂와 P₁P₃이 음의 각을 이루고 있다는 것이다.

아, 그리고 익히 약속되어 온 바, 각은 -180도부터 +180도까지의 값을 가지는 것으로 둘 것이다.

예제 1, 예제 3번의 경우를 보자. 왼쪽이 예제 1. 각이 -26.5650...°이고, 오른쪽은 예제 3. 각이 +26.5650...° 이다.

예제 1, 예제 3의 참고사진

도대체 각도랑 외적이랑 무슨 상관이냐고? 이 각의 부호가 외적의 방향을 결정짓기 때문이다!

 

두 벡터의 외적은 두 벡터에 동시에 수직인 다른 벡터이다. 그리고 그것은 평면벡터 쌍에서는, 항상 z축과 평행이게 된다.

문제는 이게 양의 z축 방향인지 음의 z축 방향인지 알 수가 없다는 거다. 방향이 두 쪽이니 알 수가 있나.

그러니 수학자들은 하나의 약속을 해 놓았다. 어떻게?

벡터의 외적은 오른손 시스템을 따르도록 말이다.

\(x\times y\)의 방향은, 오른손을 쫙 펴서 x의 방향으로 네 손가락이 향하게 둔 뒤, 그 네 손가락을 y의 방향으로 접을 수 있을 때 엄지손가락이 향하는 방향이다.

예제 1, 예제 3의 사진을 보면, 시계방향으로 배치가 되어 있을 때 외적은 -z방향. 반시계방향으로 배치가 되어 있을 때 외적은 +z방향을 나타내게 되어 있다.

 

그렇다면 곧 이 외적의 z좌표 부호가, 달리 말하자면 \(x_1y_2-x_2y_1\)의 부호가 답이라는 소리이다!

그걸 위해서 u를 벡터 P₁P₂, v를 벡터 P₁P₃로 둔 다음 그 두 벡터의 외적값을 구하면 끝이다.

그 값이 0일 경우 두 벡터가 평행하다는 뜻이고, 그 값이 플러스나 마이너스일 경우는 각각 반시계와 시계방향에 대응하니 말이다.

 

이로서 11758번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.