CCW(Counter Clock Wise) 알고리즘

3개의 점이 있을 때, 이 점을 이은 직선의 방향을 계산하는 알고리즘이다.

직선을 이은 방향은, 시계 방향, 직선 방향, 반시계 방향 중 하나로 결정된다.

 

CCW 알고리즘을 이용하여 컨벡스 헐 알고리즘(Convex Hull Algorithm) 문제를 풀 수 있다.

커넥스 헐 알고리즘은 2차원 평면상에 여러 개의 점이 있을 때, 점 중 일부를 이용하여 모든 점을 포함하는 볼록 다각형을 만드는 알고리즘이다.

 

import java.io.*;
import java.util.*;
 
public class Main_1708_볼록껍질 {
 
    // Counter Clock Wise 알고리즘, 세 점을 이은 직선의 방향 계산
    static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
        long ret = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
        if (ret > 0) { // 반시계 방향
            return 1;
        } else if (ret < 0) { // 시계 방향
            return -1;
        } else {
            return 0;
        }
    }
 
    static int sx, sy;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[][] points = new long[N][2];
 
        for (int i = 0; i < N; i++) {
            StringTokenizer token = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(token.nextToken());
            int y = Integer.parseInt(token.nextToken());
            points[i][0] = x;
            points[i][1] = y;
            if (i == 0) {
                sx = x;
                sy = y;
            } else {
                if (sy > y) {
                    sx = x;
                    sy = y;
                } else if (sy == y && sx > x)
                    sx = x;
            }
        }
 
        // 반시계 방향으로 좌표 정렬
        Arrays.sort(points, new Comparator<long[]>() {
            @Override
            public int compare(long[] o1, long[] o2) {
                int ret = ccw(sx, sy, o1[0], o1[1], o2[0], o2[1]);
                if (ret > 0) { // 반시계 방향이면 앞으로
                    return -1;
                } else if (ret < 0) { // 시계 방향이면 뒤로(위치 바꿈)
                    return 1;
                } else {// 가까운 것을 앞으로
                    long diff1 = (sx - o1[0]) * (sx - o1[0]) + (sy - o1[1]) * (sy - o1[1]);
                    long diff2 = (sx - o2[0]) * (sx - o2[0]) + (sy - o2[1]) * (sy - o2[1]);
                    return diff1 > diff2 ? 1 : -1;
                }
            }
        });
 
        Stack<long[]> st = new Stack<>();
        // 시작점 넣고 시작, 최소 1개의 점은 유지하며 탐색
        st.push(points[0]);
 
        for (int i = 1; i < N; i++) { // 다음에 탐색할 포인트
            while (st.size() > 1) { // 스택 사이즈가 1 초과일 때만 수행
                int ret = ccw(st.get(st.size() - 2)[0], st.get(st.size() - 2)[1], st.get(st.size() - 1)[0],
                        st.get(st.size() - 1)[1], points[i][0], points[i][1]);
                if (ret <= 0) // 시계 방향 또는 직선일 경우 가장 마지막에 저장한 점을 제거
                    st.pop();
                else { // 시계 방향이 생기지 않을 때 까지 반복 수행
                    break;
                }
            }
            st.push(points[i]);
        }
        System.out.println(st.size());
    }
}
 

 

해당 문제는 아래와 같다.

https://www.acmicpc.net/problem/1708

1708번: 볼록 껍질