• 점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘
• 실제 코딩 테스트에서의 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀 수 있음

CCW(Counter-ClockWise)

• 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘
• 세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라고 가정할 경우 CCW의 공식
  • CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3)

CCW 공식 도출 과정

1. 첫번재 점을 뒤에 한 번 더 쓴다.
2. 오른쪽 아래 방향 화살표 곱은 더하고, 왼쪽 아래 방향 화살표의 곱은 뺀다.

방향에 따른 CCW의 결과

• CCW 결과의 절댓값을 세 점의 백터의 외적값을 나타낸다.
• CCW의 절댓값을 절반으로 나누면 세 점으로 이뤄진 삼각형의 넓이를 나타낸다는 것을 알 수 있다.
• 즉, |CCW 결과값| / 2 는 세 점으로 이뤄진 삼각형의 넓이로 이해하면 된다.

[097] 선분 방향 구하기

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