[알고리즘] 코테 유형 분석 30. CCW

안녕하세요 이번 시간에는 CCW에 대해 알아보며 문제 유형을 분석하는 시간을 갖도록 하겠습니다.

먼저 CCW란 평명 상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘입니다. 세 점 (x1, y1), (x2, y2),(x3, y3)가 주어질 때 CCW는 다음과 같습니다.

CCW = (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3)

CCW는 결과에 따라 선분의 방향을 알 수 있습니다. CCW의 결과값이 양수라면 반시계 방향, 음수라면 시계 방향, 0이면 직선을 의미합니다.

CCW의 절댓값은 세 점의 벡터의 외적값과 같습니다. 벡터의 외적은 세 점을 가지는 평행사변형의 넓이, 즉 삼각형의 넓이의 2배와 같습니다. 즉 CCW의 절댓값 = 세 점의 벡터의 외적값 = 삼각형의 넓이 x2 = 세 점을 가지는 평행사변형 넓이로 구할 수 있습니다.

백준 11758(CCW) 문제를 통해 CCW를 구현해보겠습니다. 세 점을 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 문제입니다. CCW의 성질을 이용하여 결과값이 양수이면 반시계, 음수이면 시계, 0이면 직선을 리턴합니다.

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int px1 = Integer.parseInt(st.nextToken());
        int py1 = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int px2 = Integer.parseInt(st.nextToken());
        int py2 = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int px3 = Integer.parseInt(st.nextToken());
        int py3 = Integer.parseInt(st.nextToken());

        int ccw = (px1*py2 + px2*py3 + px3*py1) - (px2*py1 + px3*py2 + px1*py3);
        if(ccw < 0) System.out.println(-1);
        else if(ccw > 0) System.out.println(1);
        else System.out.println(0);
    }
}

첫 번째 유형은 두 선분이 교차하는지 검증하는 문제입니다. 두 점 A,B로 이루어진 선분 AB와 두 점 C,D로 이루어진 선분 CD가 존재할 때를 가정해보겠습니다. 선분 AB 기준으로 C와 D를 각각 CCW한 값의 곱과 선분 CD 기준으로 A와 B를 각각 CCW한 곱이 모두 음수이면 두 선분은 교차한다고 볼 수 있습니다. 만약 두 선분이 같은 방향의 직선일 경우 한 선분의 점 중 작은 값이 다른 선분의 큰 값보다 크다면 서로 떨어져 있는 선분으로 교차하지 않는다고 볼 수 있습니다.

백준 17387(선분 교차 2) 문제의 경우 2차원 좌표 위의 두 선분이 교차하는지를 구하는 문제입니다. 위에서 살펴본 것처럼 AB 기준으로 C와 D를 각각 CCW한 값의 곱과 CD 기준으로 A와 B를 각각 CCW한 곱이 모두 음수이면 교차한다고 판단, 직선일 경우 한 선분의 min값이 다른 선분의 max값보다 크다면 교차하지 않는다고 정의한 후 문제를 풀이합니다.

백준 2162(선분 그룹) 문제의 경우 두 선분들이 서로 만날 경우 같은 그룹에 속한다고 할 때 N개의 선분들이 총 몇 개의 그룹으로 되어있는지 구하는 문제입니다. 여러 선분들을 하나의 그룹으로 합치기 때문에 유니온 파인드 알고리즘을 사용합니다. 부모 배열을 -1로 초기화한 후 find가 부모 값이 음수라면 현재 인덱스를 리넡하고 양수라면 대표 노드를 리턴합니다. union은 두 대표 노드가 같으면 리턴, 다른 경우 대표가 될 노드에 다른 노드의 대표 노드값을 더한 후 다른 노드를 새로운 대표노드로 변경합니다. 이 과정이 반복되면 대표 노드는 음수를 가지게 되며 그 값의 절댓값이 그룹 내의 선분 수가 됩니다.

두 번째 유형은 다각형의 면적을 구하는 문제입니다. N개의 점이 주어졌을 때 N개의 점을 이웃한 순서대로 2개씩 뽑아 원점을 기준으로 CCW를 계산합니다. 이렇게 계산한 CCW값의 총 합을 절댓값으로 바꾼 후 나누기 2 연산을 통해 다각형을 구할 수 있습니다. 여기서 주의할 점은 CCW를 계산할 때마다 절댓값으로 바꾸어 합치는 것이 아니라 CCW의 총합을 절댓값으로 바꾸는 것입니다.

백준 2166(다각형의 면적) 문제의 경우 점으로 이루어진 다각형 넓이를 구하는 문제입니다. 위에서 살펴본 것처럼 각 점을 이웃한 순서대로 2개를 선택하여 원점과 CCW를 구해 그 합의 절댓값을 2로 나누어 풀 수 있습니다.