Convex Hull

Convex Hull 알고리즘은 2차원 평면에 여러 개의 점이 주어졌을 때 모든 점을 포함하는 볼록 껍질을 이루는 점들을 구하는 알고리즘입니다. 이 알고리즘의 구현에는 CCW 알고리즘이 사용됩니다.

이 알고리즘의 구현 방법은 Graham’s scan이라는 방법을 사용합니다. 이 방법의 순서는 다음과 같습니다.

(1) 2차원 평면의 점들을 정렬하고 가장 아래에 있는 점 P0를 고르고 스택에 넣습니다.(여러 개일 경우 가장 왼쪽에 있는 점)

(2) 해당 점과 나머지 점들의 기울기를 구해 x축과의 각도를 구합니다.

(3) 해당 각도를 기준으로 오름차순 정렬합니다.

(4) P0와 각도가 가장 작은 P1과 그 다음으로 작은 P2를 고릅니다. P0, P1, P2에 대해서 CCW 알고리즘을 사용하고 만약에 양수 값(반시계방향)이면 스택에 P1, P2를 넣습니다.

(5) 다음 점을 P3로 놓고, P1, P2, P3에 대해서 CCW 알고리즘을 사용합니다. 만약 0이거나 음수 값이라면 스택을 pop하고, P3를 스택에 넣어줍니다.

(6) 다음 점 P4를 놓고, P1, P3, P4에 대해서 CCW 알고리즘을 수행합니다.

이와 같이 마지막 정점 Pk까지 수행하면, 스택에 볼록 껍질을 이루는 정점이 모두 들어가게 됩니다. 다음 그림은 이러한 과정의 수행을 보여줍니다.

Convex Hull 수행 과정

아래의 코드에서는 각도 대신 cos값을 넣어주었기 때문에 그림 1과 다르게 각도를 기준으로 내림차순 하게 되고, (4),(5) 과정에서 반대가 됩니다. 따라서 시계방향일 때 스택에 넣고, 0이거나 반시계 방향이면 꺼냅니다.

import java.util.*;

class Point implements Comparable<Point> {
    double x, y;
    double scope;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
        this.scope = 0;
    }

    public int compareTo(Point P) {
        if (this.scope == P.scope) {
            if (this.y == P.y) {
                return this.x - P.x;
            }
            else {
                return this.y - P.y;
            }
        }
        else {
            return this.scope - P.scope
        }
    }
}

public class Main {
    static Point P[];

    public static int ccw(Point a, Point b, Point c) {
        Point ab = new Point(b.x - a.x, b.y - a.y);
        Point bc = new Point(c.x - b.x, c.y - b.y);
        double ret = ab.x * bc.y - ab.y * bc.x;
        if (ret > 0) return 1;
        else if (ret == 0) return 0;
        else return -1;
    }

    static int N;

    static double getDistance(Point A, Point B) {
        return Math.sqrt(Math.pow(A.x - B.x, 2.0) + Math.pow(A.y - B.y, 2.0));
    }

    static void setSlope(Point P0) {
        for (int i = 1; i < N; i++) {
            P[i].scope = (P[i].x - P0.x) / getDistance(P0, P[i]);
        }
    }

    static Stack<Integer> ConvexHull() {
        Arrays.sort(P);
        setSlope(P[0]);
        Arrays.sort(P, 1, N);
        Stack<Integer> convexhull = new Stack<>();
        convexhull.push(0);
        convexhull.push(1);

        for (int i = 2; i < N; i++) {
            while (convexhull.size() >= 2) {
                int Last = convexhull.pop();
                int pLast = convexhull.peek();
                if (ccw(P[pLast], P[Last], P[i]) < 0) {
                    convexhull.push(Last);
                    break;
                }
            }
            convexhull.push(i);
        }
        return convexhull;
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        P = new Point[N];
        for (int i = 0; i < N; i++) {
            double x = scanner.nextDouble();
            double y = scanner.nextDouble();
            P[i] = new Point(x, y);
        }
        int result = ConvexHull().size();
        System.out.println(String.valueOf(result));
    }
}