본문 바로가기

CCW2

BOJ 17386 선분 교차 1, BOJ 17387 선분 교차 2 해당 문제는 CCW를 통해 해결하는 문제이다.CCW에 대한 자세한 포스트는 카테고리 - 알고리즘 종류에서 확인 가능하다. CCW를 통해 어떻게 해결 할 수 있는지 확인해보자. 선분은 교차하는 경우와 교차하지 않는 경우로 가볍게 구분할 수 있다.각각의 방향을 따져보자. 교차하는 경우 CCW(A,B,C)는 음수 CCW(A,B,D)는 양수를 갖게 될 것이다.또 CCW(C,D,A)는 양수, CCW(C,D,B)는 음수를 갖게 될 것이다. 즉, 한 선분을 기준으로 다른 선분의 끝 점이 서로 다른 부호를 가지고 있으면 교차한다고 판단 할 수 있는 것이다. 간단히 선분 AB만 예시로 보자.그림과 같이 교차하지 않는 경우 CCW(A,B,C)와 CCW(A,B,D)는 무조건 같은 방향을 보게 될 것이다. 우리는 이제 C.. 2025. 6. 30.

CCW (Counter Clock Wise) 세 점의 방향성을 판단하는 기하학적 문제 CCW 값에 의해 세 점이 어느 방향으로 향하는지 알 수 있다. 공식은 아래와 같다.CCW(A, B, C) = (B.x - A.x) × (C.y - A.y) - (B.y - A.y) × (C.x - A.x)결과 값에 따라 양수: 반시계방향, 음수: 시계 방향, 0: 일직선을 나타낸다. CCW가 어떻게 도출되는지 알아보자.좌측 그림과 같은 좌표를 가진 세 점이 있을 때, A를 원점으로 C와 B의 벡터를 구하면 오른쪽 그림과 같이 된다. 공식은 아래와 같다.A' = (0, 0) ← A에서 A를 뺀 것B' = (bx - ax, by - ay) ← B에서 A를 뺀 것 (6, 2) 이라고 가정C' = (cx - ax, cy - ay) ← C에서 A를 뺀 것 (7, 3) 라.. 2025. 6. 30.

이전 1 다음

티스토리툴바