개발일지

개념 CCW 알고리즘을 이용하여 두 선분이 교차하는지 판별할 수 있다. 작동원리 위 예시를 보면 CCW(A, B, C)와 CCW(A, B, D)가 반대방향(곱이 음수)이면 두 선분은 교차한다고 볼 수 있다. 하지만 위 예시와 같은 반례가 존재한다. (직선이 아닌 선분이기 때문에 CCW의 방향이 반대여도 교차하지 않을 경우가 있다.) 그렇기 때문에 CCW(A, B, C)와 CCW(A, B, D)의 방향, CCW(C, D, A)와 CCW(C, D, B)의 방향 두 번을 검사하여 교차하는지 확인할 수 있다. 하지만 두 선분이 같은 직선에 있을 경우 CCW가 0이 나온다. 위와 같은 반례는 CCW(A, B, C) * CCW(A, B, D) == 0 && CCW(C, D, A) * CCW(C, D, B) == 0..

개념 Counter Clock Wise 알고리즘의 줄임말이다. 세 점의 외적의 성질을 이용하는 알고리즘으로 보통 세점의 방향이 시계, 반시계, 직선인지 판별한다. 또한 외적의 성질을 이용하여 세 점이 이루는 삼각형의 넓이를 알 수 있다. 작동원리 세 점을 크로스 곱하여 그 값이 양수면 반 시계, 0이면 직선, 음수면 시계방향이다. 크로스 곱하여 2로 나누면 세 점이 이루는 삼각형의 크기이다. 시간복잡도 세 점을 외적할 때 -> 1 -> O(1) 문제 11758 CCW www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2,..