문제
#11758: CCW
첫 번째 행의 P1(x1, y1), 두 번째 행의 P2(x2, y2) 및 세 번째 행의 P3(x3, y3). (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수입니다. P1, P2 및 P3의 좌표가 다릅니다.
www.acmicpc.net
설명
CCW는 Counter Clock Wise의 약자로 문자 그대로 “시계 반대 방향”을 의미합니다.
세 점이 주어진 직선 방향을 찾는 데 사용되는 알고리즘.
위의 이미지를 보면 “왜 저게 반시계 방향이지?”라고 생각할 수 있으니 수학적으로 설명해보자.
CCW
먼저 방향을 찾는 공식은 $(x2 – x1) * (y3 – y1) – (y2 – y1) * (x3 – x1)$입니다.
사진 자료는 (알고리즘) CCW(Counter Clock Wise) (tistory.com) 블로그에서 가져왔습니다.
다음은 점 A(10, 15), B(5, 10) 및 C(8, 5)입니다.
직선 C → A → B가 어느 방향으로 가는지 알아봅시다.
C와 A를 연결하는 벡터 CA와 A와 B를 연결하는 벡터 AB를 만듭니다. 그리고 벡터 CA와 AB의 외적을 찾으십시오.
각 벡터의 좌표를 찾으려고 했습니다.
좌표는 거리를 빼서 구합니다. z축이 없으므로 0을 넣었습니다. 이제 우리가 해야 할 일은 벡터의 외적을 찾는 것입니다.
벡터의 외적은 위와 같이 구합니다.
그러면 공식이 있습니다.
직선은 양수이므로 시계 반대 방향임을 알 수 있습니다.
#include <iostream>
using namespace std;
int main() {
int x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
int direction = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
if (direction < 0) cout << "-1";
else if (direction > 0) cout << "1";
else cout << "0";
return 0;
}