CCW 알고리즘(CCW Algorithm)
최근에 배우게 된 CCW 알고리즘에 대해 글을 써보고자 한다. CCW 알고리즘이란? Counter-ClockWise의 줄임말로, 직역하면 반시계 방향이라는 뜻임. 세 점 p1, p2, p3가 주어져 있고, 이 세 점을 p1, p2, p3 순서대로 직선으로 이었을 때, 시계방향으로 휘어지는가, 반시계 방향으로 휘어지는가, 혹은 일직선을 이루는가를 판별하는 알고리즘. 방향이 중요하기 때문에 벡터의 개념을 알아야 함. 이 알고리즘을 활용하여 다양한 기하학 알고리즘에 적용할 수 있음. 대표적으로 선분 교차 판정 알고리즘, 볼록 껍질 알고리즘(컨벡스 헐) 등이 있음. 요약된 내용으로만 보아서는 무슨 뜻인지 잘 모를 수도 있을 것이다. 그래서 다음과 같이 그림을 준비했다. 위의 그림처럼 세 점 P1, P2, P3를..
[Python] 2013번 선그리기
https://www.acmicpc.net/problem/2013 2013번: 선그리기 첫째 줄에 선분의 개수 N(1 p2[0]: return p1 elif p1[0] = p2[1]: return p1 else: return p2 def point_swap(p1, p2): if point_compare(p1, p2) == p1: return p2, p1 else: return p1, p2 def line_swap(p1, p2, p3, p4): if point_compare(p1, p3) == p1: return p3, p4, p1, p2 else: return p1, p2, p3, p4 def can_draw_once(line1, line2)..
