[BOJ] 1708 볼록 껍질 (JAVA)

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

1708번: 볼록 껍질

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static Pos[] input;
    static Pos first = new Pos(50000, 50000);

    public static void main(String[] args) throws Exception {

        N = Integer.parseInt(br.readLine());
        input = new Pos[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            input[i] = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < N; i++) {
            if (input[i].y < first.y || (input[i].y == first.y && input[i].x < first.x)) first = input[i];
        }

        Stack<Pos> stack = new Stack<>();
        Arrays.sort(input);
        stack.push(first);
        stack.push(input[1]);

        for (int i = 2; i <N; i++) {

            while (1 < stack.size()) {

                Pos two = stack.pop();
                Pos one = stack.peek();

                if (0 < ccw(one, two, input[i])) {
                    stack.push(two);
                    break;
                }

            }

            stack.push(input[i]);

        }

        System.out.print(stack.size());

    }

    static int ccw(Pos a, Pos b, Pos c) {
        long result = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

        if (0 < result) return 1;
        else if (result < 0) return -1;
        return 0;
    }

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

    static class Pos implements Comparable<Pos> {

        long x, y;

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

        @Override
        public int compareTo (Pos o) {
            int result = ccw(first, this, o);
            if (0 < result) return -1;
            else if (result < 0) return 1;
            else if (dist(first, o) < dist(first, this)) return 1;
            return -1;
        }
    }

}