Geometry

Convex Hull

• 컨백스 헐이란?
• reference

1. list[] 에 있는 점들 중 가장 작은 것을 찾아서 기준점으로 선정한다.
2. 기준점 기준으로 각각의 점들을 반시계 방향으로 기준점과 각도 순서대로 정렬한다.
3. 점들을 하나씩 보면서 볼록껍질에 포함시킬지 말지를 결정한다.
4. 스택을 하나 만들고, 이 스택에는 점의 번호를 넣어주는데 스택 사이즈가 한개밖에 없으면 일단 지금 잡고 있는 점을 넣는다.
5. 스택에 점이 두 개 이상이면 비교를 한다.
6. 점 두개를 기준으로 다른 점을 봤을 때 CCW를 하는데, 이 때 반시계 방향에 있으면 만족하므로 스택에 넣어준다.
7. 그리고나서 또 스택의 두개를 빼서 두 점 기준으로 다음 점을 CCW 한다.
8. 만약 반시계 방향에 없다면 오목하다는 의미이므로 만족하지 않는다. 따라서 이럴 경우에는 스택에서 빼준다.
9. 이렇게 계속 반복해준다.

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

class Point {
    long x;
    long y;

    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        ArrayList points = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            String belong = st.nextToken();

            if (belong.equals("Y")) {   // Y인 것만 볼록 껍질
                points.add(new Point(x, y));
            }
        }

        Stack result = grahamScan(points);
        bw.write(result.size() + "\n");

        for (int i = 0; i < result.size(); i++) {
            bw.write(result.get(i).x + " " + result.get(i).y + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    static Point root = new Point(Long.MAX_VALUE, Long.MAX_VALUE);

    static Stack grahamScan(ArrayList input) throws IOException {

        // 기준점 찾기
        for (int i = 0; i < input.size(); i++) {
            if (input.get(i).x < root.x) {
                root = input.get(i);
            } else if (input.get(i).x == root.x) {
                if (input.get(i).y < root.y) {
                    root = input.get(i);
                }
            }
        }

        // 모든 점들을 반시계 방향으로 정렬하기
        input.sort(new Comparator() {
            @Override
            public int compare(Point p1, Point p2) {    // return 1이면 자리를 바꾼다
                int result = ccw(root, p1, p2);

                if (result > 0) {
                    return -1;
                } else if (result < 0) {
                    return 1;
                } else {
                    long distance1 = dist(root, p1);
                    long distance2 = dist(root, p2);

                    if (distance1 > distance2) {    // 거리가 더 가까운 순으로 정렬
                        return 1;
                    }
                }
                return -1;
            }
        });

        Stack stack = new Stack<>();
        stack.add(root);

        for (int i = 1; i < input.size(); i++) {
            while (stack.size() > 1 && (ccw(stack.get(stack.size() - 2), stack.get(stack.size() - 1), input.get(i)) < 0)) {    // first, second, next
                stack.pop();    // second 빼기
            }
            stack.add(input.get(i));    // next 넣기
        }

        ArrayList extra_points = new ArrayList<>();

        // input에 있는 값인데 stack에 없는 경우 추가해줘야함
        for (int i = 1; i < input.size(); i++) {
            if (!stack.contains(input.get(i))) {
                extra_points.add(input.get(i));
            }
        }

        extra_points.sort(new Comparator() {
            @Override
            public int compare(Point o1, Point o2) {
                long distance1 = dist(root, o1);
                long distance2 = dist(root, o2);

                if (distance1 < distance2) {
                    return 1;
                }
                return -1;
            }
        });

        stack.addAll(extra_points);

        return stack;
    }

    static int ccw(Point p1, Point p2, Point p3) {
        long result = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

        if (result > 0) {   // 반시계 방향
            return 1;
        } else if (result < 0) {    // 시계 방향
            return -1;
        } else {
            return 0;
        }
    }

    static long dist(Point p1, Point p2) {
        return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
    }
}

출처