[D-day] 기하

📍 기하

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

📍 CCW

✅ 정의

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

✅ CCW 공식 도출 과정

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

평면 상의 세 개의 점

신발끈 공식

대입

✅ 방향에 따른 CCW의 결과

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