Convex Hull

주어진 점들을 이용한 볼록 다각형을 구하는 문제이다.

 

이렇게 말이다.

 

이 구하는 방법을 생각해보면

 

1. 점들을 입력 받는다.

 

2. 기준점을 구한다. 기준점은 y좌표가 작은순 -> x좌표가 작은순 이다. 즉 (x,y) 좌표가 제일 작은 것이다.

그러면 기준점을 기준으로 다른 점들은 항상 북동쪽에 위치해 있을것이다. 왜냐? 기준점은 x,y 좌표가 제일 작은 값이니깐... 

 

3. 이제 이것을 정렬을 시키는데 조건이라면

 - 기준점과 나머지점들이 ccw로 반시계방향(좌회전)이 되도록 정렬

 - 만약 일직선상에 있으면 거리가 증가하게끔 정렬을 시킴 

 

이것의 정렬결과는 대충 그림으로 나타내면 밑의 그림과 같이 탐색하는 방식이 된다.

4. 정렬된 점을 그라함 스캔 한다. (제일 중요함!!)

그라함 스캔은

1. 스택을 만든다.

2. 점 탐색시 스택의 size가 2 미만이면 이 점을 스택에 넣는다.

3. 스택의 size가 2 이상이라면 

  a점 : stack의 2번째 top

  b점 : stack의 top

  c점 : 탐색점 

 이 세 점을 ccw(a,b,c) 해서 반시계가 나오면 c점(탐색점) 을 stack에 넣는다.

                                   0이나 시계가 나오면 b점을 버린다.

 

 

대충 그림을 그려보자.

1번점, 2번점은 그냥 쌓일것이고

3번점은 그냥 눈으로만 봐도 반시계니 3번까진 그냥 넘기고 4번부터 보자.

(1~5번점은 3번의 과정을 거쳐서 정렬된 상태이다.)

 

 

 

이것을 코드로 구현해 보자.

 

www.acmicpc.net/problem/1708

1708번: 볼록 껍질

베이스는 이 문제이다.

 

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210420_boj1708_볼록껍질 {
 
    //first = y좌표가 가장 작은 점이나  x좌표값이 가장 작은 점을 기준점으로 잡음
    static Point first = new Point(Long.MAX_VALUE, Long.MAX_VALUE);
    
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ArrayList<Point> arr =  new ArrayList<Point>();
        // 1. 점들을 입력받는다.
        int n = Integer.parseInt(br.readLine());
        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());
            arr.add(new Point(x, y));
        }
        
        // 2. 기준점을 구한다.기준점은 y좌표가 작은순 -> x좌표가 작은 순
        for(int i = 0 ; i < arr.size(); i++) {
            if(arr.get(i).y < first.y)
                first = arr.get(i);
            else if(arr.get(i).y == first.y &&  arr.get(i).x < first.x)
                first = arr.get(i);
        }
        
        //3. 기준점과 나머지점들이 ccw로 반시계방향(좌회전)이 되도록 정렬을 시키고, 만약 일직선상에 있으면 거리가 증가하게끔 정렬을 시킴 
        Collections.sort(arr, new Comparator<Point>() {
 
            @Override
            public int compare(Point second, Point third) {
                int ccw_Result = ccw(first, second, third);
                
                if(ccw_Result > 0)
                    return -1; // second -> third
                else if(ccw_Result < 0)
                    return 1; // third -> second
                else{
                    long dist1 = dist(first, second);
                    long dist2 = dist(first, third);
                    return Long.compare(dist1, dist2);
                }
            }
            
        });
        
        /*
        for(int i = 0 ; i < arr.size(); i++)
            System.out.println(arr.get(i).x + " " + arr.get(i).y);
        */
        
        
        
        //4. 그라함 스캔 Start
        Stack<Point> s = new Stack<Point>();
        s.add(first);
        
        for(int i = 1 ; i < arr.size(); i++) {
            while(s.size() > 1 && ccw(s.get(s.size()-2), s.get(s.size()-1), arr.get(i)) <= 0)
                s.pop();
            s.add(arr.get(i));
        }
        
        /*
        //ArrayList 그라함 스캔인데 위에 스택보다 좀더 빠르게 나온다. 
        ArrayList<Point> s= new ArrayList<Point>();
        s.add(first);
        
        for(int i = 1 ; i < arr.size(); i++) {
            while(s.size() > 1 && ccw(s.get(s.size()-2), s.get(s.size()-1), arr.get(i)) <= 0)
                    s.remove(s.size()-1);
            s.add(arr.get(i));
        }
        */
        
        
        System.out.println(s.size());
        
    }
    
    
    static class Point {
        long x;
        long y;
        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
        
    }
    static int ccw(Point a , Point b , Point c) {
        long n = (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 (n > 0)
            return 1;
        else if (n < 0)
            return -1;
        else
            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);
        }
    
}