Geometry

Convex Hull

• 컨백스 헐이란?
• reference

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;
 
class Hull{
    int x, y;
    Hull(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class temp {
    static int N;
    static Hull list[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        list = new Hull[N+1];
        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            list[i] = new Hull(a, b);
        }
        // 1. 기준점 선정
        for(int i=1; i<=N; i++){
            if(list[1].y > list[i].y || list[1].y == list[i].y && list[1].x > list[i].x){
                Hull temp = list[1];
                list[1] = list[i];
                list[i] = temp;
            }
        }
        
        // 2. 기준점 기준으로 반시계방향으로 정렬
        Arrays.sort(list, 2, N+1, new Comparator() {
 
            @Override
            public int compare(Hull a, Hull b) {
                // TODO Auto-generated method stub
                int v = ccw(new Hull(list[1].x, list[1].y), a, b);
                if( v > 0)    return -1;
                if(v<0)    return 1;
                return (Math.abs(a.x) + a.y) - (Math.abs(b.x) + b.y);
            }
        });    
        // 3. stack 
        Stack stack = new Stack<>();
        stack.push(1);
        for(int i=2; i<=N; i++){
            while(stack.size() > 1 && ccw(list[stack.get(stack.size()-2)], list[stack.peek()], list[i]) <=0 ){
                stack.pop();
            }
            stack.add(i);
        }
        bw.write(stack.size() + "\n");
        bw.flush();
    }
    protected static int ccw(Hull A, Hull B, Hull C) {
        long cal = 0;
        cal = (long)(B.x - A.x) * (C.y - A.y) - (long)(C.x-A.x) * (B.y-A.y);
        if(cal > 0)    return 1;
        else if (cal< 0)    return -1;
        else    return 0;
    }
}

출처