CCW 썸네일형 리스트형 2162번: 선분 그룹 - Baekjoon Online Judge 선분 그룹이라는 문제는 기하 알고리즘 문제풀이의 기초이자 꽃이라고 할 수 있는 CCW를 이용하는 동시에 유니온 파인드를 섞어 놓은 문제였다. 문제를 보면서 대충 어떤 식으로 풀면되겠다는 것이 머리 속에 그려져서 로직도 금방 세우고 코딩도 금방했는데 의외로 계속 오답이 나서 짜증나는 문제였다. 문제를 살펴보면 여러 선분이 주어졌을 때, 만일 선분끼리 교차되거나 겹치게 되면 그 선분들은 하나의 그룹이 된다. 이 때 선분들을 몇 개의 그룹으로 묶을 수 있고 그룹 중에 가장 많은 선분을 포함하고 있는 그룹에 속한 선분이 몇 개인지 출력하면 된다. 문제를 보고 생각난 것은 CCW였다. 기하 문제를 풀어본 사람은 알겠지만, CCW를 이용하면 두 선분의 교차 여부를 쉽게 파악할 수 있다. 만일 CCW가 익숙하지 않은.. CCW(CounterClockWise) 알고리즘 CCW(CounterClockWise)는 외적을 이용해서 두 벡터의 상대적 위치를 파악하는 알고리즘이다. 좀더 구체적으로 설명하자면 하나의 정점을 기준으로 다른 두 정점으로 향하는 벡터가 존재할 때 각 정점의 상대적 위치를 판단하는 공식이다. 만일 하나의 정점에서 다른 정점으로 향하는 벡터를 기준으로 왼쪽에 존재하는 정점의 경우 외적은 양의 값을 갖게 되고, 상대적으로 우측에 있게 되면 외적은 음의 값을 갖게된다. 마지막으로 세 점이 하나의 직선 위에 놓이게 되었을 때 외적은 0이 된다. 이를 이용하여 다각형의 넓이 구하기, 정점의 위치판단(다각형 내부/외부 위치 구분), 볼록다각형 그리기(Convex Hull) 등 다양한 기하 문제를 풀어낼 수 있다. 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세.. 이전 1 다음