[백준 - 1708번] 볼록 껍질 - Java //Wello Horld//

이번에는 BOJ의 1708번 문제 "볼록 껍질"을 풀어보도록 하자

이 문제는 Convex Hull Algorithm(볼록 껍질 알고리즘)의 기초 문제이다. 일단, 입력으로 점의 개수 N이 주어지고, 둘째 줄부터 N줄 만큼 각 점의 x, y좌표가 공백을 사이에 두고 주어진다. (단, 각 점의 좌표는 다르다.) 출력으로는 볼록껍질을 이루는 점의 개수를 출력하면되는 문제이다.(단, 볼록껍질의 변에 점이 여러개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.)

성공한 코드는 아래와 같다. 오버플로우 때문에, 점의 x, y좌표는 모두 long으로 받아줬다. 그렇게 하지않으면, 제출시 런타임 오류가 뜨게 된다.

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

public class sample {
    //x좌표와 y좌표의 절대값은 40,000을 넘지 않는다
    static Point first = new Point(40001, 40001);
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        ArrayList<Point> points = new ArrayList<Point>();
        //입력으로부터 각 점들의 x, y좌표를 받아옴
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            points.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        //y좌표가 가장 작은 점이나, 점들 중에서 x좌표값이 가장 작음 점을 기준점으로 잡음
        for (int i = 0; i < points.size(); i++) {
            if (points.get(i).y < first.y) {
                first = points.get(i);
            } else if (points.get(i).y == first.y) {
                if (points.get(i).x < first.x) {
                    first = points.get(i);
                }
            }
        }
        //기준점과 나머지점들이 ccw로 반시계방향(좌회전)이 되도록 정렬을 시키고, 만약 일직선상에 있으면 거리가 증가하게끔 정렬을 시킴 
        points.sort(new Comparator<Point>() {
            @Override
            public int compare(Point second, Point third) {
                int ccwR = ccw(first, second, third);
                if (ccwR > 0)
                    return -1;
                else if (ccwR < 0)
                    return 1;
                else if (ccwR == 0) {
                    long distR1 = dist(first, second);
                    long distR2 = dist(first, third);
                    if (distR1 > distR2)
                        return 1;
                }
                return -1;
            }
        });

        //그라함 스캔 알고리즘
        Stack<Point> stack = new Stack<Point>();
        stack.add(first);
        for(int i = 1; i < points.size(); i++){
            while(stack.size() > 1 && ccw(stack.get(stack.size() - 2), stack.get(stack.size() - 1), points.get(i)) <= 0){
                stack.pop();
            }
            stack.add(points.get(i));
        }
        bw.write(stack.size() + "\n");

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

    static int ccw(Point a, Point b, Point c) {
        long ccwR = (a.x * b.y + b.x * c.y + c.x * a.y) - (b.x * a.y + c.x * b.y + a.x * c.y);
        if (ccwR > 0)
            return 1;
        if (ccwR < 0)
            return -1;
        return 0;
    }

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

    static class Point {
        long x, y;

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

 

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

1708번: 볼록 껍질