95. Counterclockwise Function

기하 문제를 풀 때 필요한 가장 기본적인 개념 중 하나가 CCW 함수(Counterclockwise Function)이다. 이 함수는 $x$축, $y$축이 존재하는 $2$차원 평면상의 세 점 $\text{A}(x_1, y_1), \text{B}(x_2, y_2), \text{C}(x_3, y_3)$가 주어졌을 때 점 $\text{C}$가 벡터 $\overset{\longrightarrow}{\text{AB}}$를 기준으로 왼쪽(반시계 방향, CCW)/오른쪽(시계 방향, CW) 중 어느 쪽에 있는지를 판별하는 함수이다. 확인 대상이 점인 경우 판별이 막연할 수 있으나 확인 대상을 점 $\text{C}$ 대신 벡터 $\overset{\longrightarrow}{\text{AC}}$로 해도 결과가 같기 때문에 확인 대상을 벡터로 바꾸면 판별이 간단해진다.

 

CCW 함수는 두 벡터의 외적을 이용해서 방향을 판별한다. 평면상에 존재하는 두 벡터의 외적은 두 벡터에 모두 수직인 벡터로 나타낼 수 있으므로 두 벡터가 평행하지 않은 이상 $xy$ 평면에 수직인 벡터가 외적의 결과가 되는데, 이 벡터의 $z$성분의 부호가 오른손 법칙을 따르기 때문에 부호를 확인하면 두 벡터의 방향 관계를 파악할 수 있는 것이다.

 

$2$차원 평면상의 점은 $z$좌표가 $0$인 $3$차원 공간상의 점으로 간주할 수 있으므로 벡터 $\overset{\longrightarrow}{\text{AB}}$와 $\overset{\longrightarrow}{\text{AC}}$를 각각 $3$차원 벡터로 간주할 수 있다. 또한 $3$차원 공간의 벡터 $\overset{\rightarrow}a = (a_x, a_y, a_z), \overset{\rightarrow}b = (b_x, b_y, b_z)$의 외적은 다음과 같이 정의된다. 보통 벡터를 나타낼 때 $\overset{\rightarrow}u$나 $\overset{\rightarrow}v$를 많이 사용하지만 여기서 그것들을 쓰면 가독성이 심하게 떨어지므로 $\overset{\rightarrow}a$와 $\overset{\rightarrow}b$로 표기하기로 한다.

$$\overset{\rightarrow}a \times \overset{\rightarrow}b = (a_yb_z - a_zb_y, a_zb_x - a_xb_z, a_xb_y - a_yb_x)$$

위 식에 $\overset{\rightarrow}a = (x_2 - x_1, y_2 - y_1, z_2 - z_1)$, $\overset{\rightarrow}b = (x_3 - x_1, y_3 - y_1, z_3 - z_1)$을 대입하면 $z_1 = z_2 = z_3 = 0$이므로 두 벡터의 외적은 다음과 같이 간단하게 표현된다.

$$\overset{\longrightarrow}{\text{AB}} \times \overset{\longrightarrow}{\text{AC}} = (0, 0, (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1))$$

오른손 법칙에 의해서 외적의 $z$성분의 부호가 $+$이면 CCW, $-$이면 CW라는 결과를 얻을 수 있다. $z$성분이 $0$인 경우는 두 벡터가 평행한 것이다. 또한 $z$성분의 절댓값 자체는 세 점 $\text{A}, \text{B}, \text{C}$로 이루어지는 삼각형의 넓이의 두 배와 같기 때문에 CCW 함수를 이용해서 다각형의 면적을 구할 수도 있다.

 

구현은 단순히 위의 수식을 옮기기만 하면 끝난다.

typedef long long LL;
LL ccw(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3){return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);}

 

[연습문제]

 

BOJ 11758. CCW (Gold V)

CCW 함수를 구현하는 문제이다.

 

BOJ 2166. 다각형의 면적 (Gold V)

연속된 세 점 사이의 CCW 값을 모두 더한 뒤 절댓값으로 바꿔서 $2$로 나누면 답이 나온다. 각각의 CCW 값이 양수일 수도 있고 음수일 수도 있으나 이 부호 자체가 점들의 방향성을 알려주는 것이므로 그냥 다 더하면 된다.