문제 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 해결 방법 이 문제를 풀기 위해 두가지 알고리즘을 알아야 함 CCW를 사용해 두 선분이 겹치는지 판단 Union-Find를 통해 그룹을 합치고 확인하는 작업 진행 위 두 알고리즘을 알고 같이 사용한다면 쉽게 해결할 수 있음 입력받은 모든 선분들끼리 서로 겹치는지 판단 선분이 겹치는지는 CCW를 통해 판단 두 선분이 겹친다면 Union 과정 진행 위 작업이 끝..

CCW 설명 및 백준 2166번 문제 풀이 https://chb2005.tistory.com/87 [JAVA] CCW CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*.. chb2005.tistory.com

CCW 설명 및 백준 17387번 문제 풀이 https://chb2005.tistory.com/87 [JAVA] CCW CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*.. chb2005.tistory.com

CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*Y1 + X3*Y2 + X1*Y3 ) 공식을 따로 외울 필요없이 아래 그림처럼 X1, Y1을 한 번 더 쓴 후, 검은 화살표 곱은 더하고 빨간 화살표 곱은 빼주면 됨 계산된 CCW 값으로는 2가지를 알 수 있음 CCW의 부호에 따라 시계방향, 반시계방향, 일직선의 위치관계에 있는지 파악 가능 CCW 시계 방향 CCW == 0 => 일직선 CCW > 0 => 반시계 방향 CCW의 절대값은 세 점의 벡터의 외적값을 나타냄..