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

Thumbnail: Photo by 愚木混株 Yumu (Unsplash)

세 점에 대한 방향 관계를 구하는, CCW 알고리즘 풀이의 정석적인 문제입니다.

풀이

CCW?

CCW는 Counter Clockwise의 약자로, 임의의 세 점 A, B, C를 순서대로 볼 때, 세 점의 연결 방향이 시계 방향인지 반시계 방향인지 판단하는 알고리즘입니다.

CCW는 벡터의 외적을 통해 계산한 결과로 세 점의 연결 방향을 알아냅니다.

벡터 기초

외적에 대해 알아보기 전에, 먼저 벡터에 관한 기본 개념을 정리해봅시다.

1. 벡터의 외적은 \(\times\)로 표기합니다.
   외적의 결과는 외적의 계산에 사용된 두 벡터에 동시에 수직인 벡터입니다.
   CCW 알고리즘은 이 외적의 결과 벡터의 방향을 통해 세 점의 방향 관계를 판단합니다.
2. 외적은 교환법칙이 성립하지 않습니다. 즉, \(\vec{a} \times \vec{b} \ne \vec{b} \times \vec{a}\)입니다.
   사실, \(\vec{a} \times \vec{b} = -(\vec{b} \times \vec{a})\)입니다. 즉 반대로 외적을 취할 시 크기는 같지만 방향이 반대인 결과를 얻을 수 있습니다.
3. 모든 성분이 0인 벡터를 0 벡터라고 하며, \(\vec{0}\)으로 표기합니다.
   또한, 스칼라 0과 임의의 벡터 \(\vec{v}\)에 대해
   \(0 \cdot \vec{v} = \vec{0}\)입니다.
4. 길이가 1인 벡터를 단위벡터 (unit vector)라고 합니다.
   x, y, z축의 양의 방향으로 향하는 단위 벡터를 각각 \(\vec{i}, \vec{j}, \vec{k}\)라고 하겠습니다.

벡터의 외적?

\(\vec{n}\)을 두 벡터 \(\vec{a}, \vec{b}\)에 수직인 단위벡터라 하고 \(\theta\)를 두 벡터가 이루는 각이라고 하면, 두 벡터 \(\vec{a}, \vec{b}\)의 외적은 다음과 같습니다.
\(\vec{a} \times \vec{b} = (|\vec{a}||\vec{b}|sin{\theta}) \cdot \vec{n}\), \((0 \le \theta \le \pi)\)

먼저, \(\theta = 0\) 또는 \(\theta = \pi\)인 경우를 알아봅시다. 이 경우, \(sin \theta\)가 0이 되므로

$$\begin{equation}\nonumber\begin{split}\vec{a}\times\vec{b}&=(|\vec{a}||\vec{b}|sin{\theta})\cdot\vec{n}\\&=(|\vec{a}||\vec{b}|\times 0)\cdot\vec{n}\\&=0\cdot\vec{n}\\&=\vec{0}\end{split}\end{equation}$$

두 벡터 \(\vec{a}, \vec{b}\)의 외적의 결과는 0이 됩니다.
\(\theta=0\) 또는 \(\theta=\pi\)인 경우는 두 벡터 \(\vec{a}, \vec{b}\)가 일직선 상에 위치한 경우이므로, 외적의 결과가 0인 경우 세 점은 한 직선 위에 있다고 판단할 수 있습니다.

그 외의 경우는 어떻게 될까요? 두 벡터 \(\vec{a}, \vec{b}\)의 성분을 각각 \(\vec{a}=(m_{1},m_{2},m_{3}), \vec{b}=(n_{1},n_{2},n_{3})\)이라고 정의하고 외적을 계산해봅시다.

$$\begin{equation} \nonumber \begin{split} \vec{a} \times \vec{b} &= \begin{vmatrix} \hat{i} & \hat{j} & \hat{k} \\ m_{1} & m_{2} & m_{3} \\ n_{1} & n_{2} & n_{3} \end{vmatrix} \\ &= \begin{vmatrix} m_{2} & m_{3} \\ n_{2} & n_{3} \end{vmatrix} \hat{i} - \begin{vmatrix} m_{1} & m_{3} \\ n_{1} & n_{3} \end{vmatrix} \hat{j} + \begin{vmatrix} m_{1} & m_{2} \\ n_{1} & n_{2} \end{vmatrix} \hat{k} \\ &= (m_{2}n_{3}-m_{3}n_{2}, m_{3}n{1}-m_{1}n_{3}, m_{1}n_{2}-m_{2}n_{1}) \end{split}\end{equation}$$

이때, 세 점 모두 2차원 평면 위에 위치하므로 두 벡터 \(\vec{a}, \vec{b}\)의 z축 성분 \(m_{3}, n_{3}\) 모두 0입니다. 다시 식을 정리하면, 외적의 결과로 얻은 벡터는 \((0, 0, m_{1}n_{2}-m_{2}n_{1})\)이 됩니다.

따라서, 외적의 결과로 얻은 z축 성분을 활용해 세 점 A, B, C의 방향 관계를 알아낼 수 있습니다! 이는 오른손 법칙으로 이해하면 됩니다.

그림 출처: STPM Further Mathematics T - 12.1 – 3D Vectors

외적을 통해 얻은 z축 성분을 \(D = m_{1}n_{2} - m_{2}n_{1}\)라고 할 때, D의 부호에 따라 세 점 A, B, C의 방향 관계는 다음과 같이 결정됩니다.

• \(D > 0\)일 때, 반시계 방향입니다.
• \(D = 0\)일 때, 평행합니다. (세 점 A, B, C는 한 직선 상에 있습니다.)
• \(D < 0\)일 때, 시계 방향입니다.

사선 공식?

앞서 구한 벡터의 외적을 다시 살펴봅시다.

세 점 A, B, C의 좌표를 다음과 같이 정의했을 때,

$$\begin{align} \nonumber A &= (x_{1}, y_{1}, 0) \\ \nonumber B &= (x_{2}, y_{2}, 0) \\ \nonumber C &= (x_{3}, y_{3}, 0)\end{align}$$

두 벡터 \(\vec{AB}, \vec{AC}\)은 다음과 같습니다.

$$\begin{align}\nonumber \vec{AB} &= (x_{2}-x_{1}, y_{2}-y_{1}, 0) \\ \nonumber \vec{AC} &= (x_{3}-x_{1}, y_{3}-y_{1}, 0)\end{align}$$

위에서 외적의 결과를 정리했던 식을 토대로,
\(\vec{AB} \times \vec{AC} = (0, 0, (x_{2}-x_{1})(y_{3}-y_{1}), (x_{3}-x_{1})(y_{2}-y_{1})\)임을 알 수 있습니다.

이제 \((x_{2}-x_{1})(y_{3}-y_{1}), (x_{3}-x_{1})(y_{2}-y_{1})\)을 정리해봅시다.

$$\begin{equation} \nonumber (x_{2}-x_{1})(y_{3}-y_{1}) - (x_{3}-x_{1})(y_{2}-y_{1}) = x_{1}y_{2} + x_{2}y_{3} + x_{3}y_{1} - y_{1}x_{2} - y_{2}x_{3} - y_{3}x_{1} \end{equation}$$

유도된 공식을 보면, 삼각형 넓이 계산에 자주 사용했던 사선 공식과 동일합니다!
사선 공식은 다음과 같이 진행됩니다.

1. 먼저 각 좌표들을 행렬의 형태로 배치합니다.
   $$\begin{vmatrix} x_{1} & x_{2} & x_{3} & x_{1} \\ y_{1} & y_{2} & y_{3} & y_{1} \end{vmatrix}$$
2. 먼저 빨간 빗금대로 각각 곱해서 더해줍니다.
   \(x_{1}y_{2} + x_{2}y_{3} + x_{3}y_{1}\)이 됩니다.

3. 이후, 파란 빗금대로 각각 곱해서 빼주면 됩니다.
   \(- y_{1}x_{2} - y_{2}x_{3} - y_{3}x_{1}\)

CCW로 삼각형의 넓이 구하기

CCW를 응용해 삼각형의 넓이를 구할 수 있습니다. 관련해서는 다른 글에서 추가로 설명하겠습니다.

전체 코드

input = open(0).readline
P = [tuple(map(int, input().split())) for _ in range(3)]

# D = x1y2 + x2y3 + x3y1 - y1x2 -y2x3 - y3x1
D = P[0][0] * P[1][1] + P[1][0] * P[2][1] + P[2][0] * P[0][1] - P[0][1] * P[1][0] - P[1][1] * P[2][0] - P[2][1] * P[0][0]

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