[KOITP] Convex Hull

출    처 : http://koitp.org/problem/CONVEXHULL/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1523	208 (14%)	147

문제

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (Convex Hull) 이라 한다.

N개의 점이 주어질 때 볼록껍질을 이루는 점의 개수를 구하여라. 만약 볼록껍질을 이루는 한 선분에 3개 이상의 점이 포함된 경우, 양 끝점만을 센다.

입력

첫 번째 줄에 점의 개수 N이 주어진다. (3 ≤ N ≤ 100,000)

두 번째 줄부터 N개의 줄에 걸쳐 각 점의 좌표를 의미하는 두 정수 x, y가 공백으로 분리되어 주어진다. (-40,000 ≤ x, y ≤ 40,000) 각 점은 모두 다른 위치에 있으며, 모든 점이 한 직선위에 있는 경우는 없다.

출력

첫 번째 줄에 볼록껍질을 이루는 점의 개수를 출력한다.

힌트

예제 입력

8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2

예제 출력

5

< Comment >

 다른 것은 둘째 치더라도, Exception 이 어디에서 발생하는지 몰라 한참을 헤매었습니다. 이클립스상에서는 별 문제없이 수행되었으나, 이클립스 역시도 랜덤하게 값을 생성하여 입력하니 드문드문 에러가 발생했습니다.

 찾아보니 compare를 재정의 하는 경우 jdk 1.7 버전의 에러라고 하기에 해당 부분을 수차례 수정하였으나, 결과가 달라지지 않았었습니다. 결론적으로는 제가 코딩하는 부분에 오류가 있었기 때문이었습니다.

 원래는 입력을 다 받고 난 후에, 0 ~ N-1까지의 점에 대하여 0번을 빼주는 작업을 했었는데, 이게 처음에 0번값을 빼주어 points[0] 값이 (0, 0) 이 되고, 원래 값은 다른 값이다 보니, 해당 부분에서 Exception 이 발생한 것이었습니다.

 알고나니 허무하기도 하고 하지만, 기본적으로 Convex Hull 같은 기하문제는 처음 본 것이고, ccw 등을 이용하는 방법들을 배울 수 있는 기회가 되었습니다. ccw 는 반시계방향을 의미하는데, 어떤 지점 a로부터 b와 c가 있고, a에서 b로 가는 벡터와 a에서 c로 가는 벡터를 외적하는 것을 보통 ccw 함수라고 부르고, a-b 직선에 대해서 c가 ccw에 있는지 cw(시계방향) 에 있는지 음수 혹은 양수인가를 통해 판별할 수 있어서, 기하문제에 많이 이용되는 것 같습니다. 이외에도 다른 문제들에서 Convex Hull 을 이용한 유사 알고리즘을 구현하는 경우도 있었습니다.

 발상은 처음에는 배우지 않고 이런걸 풀 수가 있나 싶었습니다. 우선 y축상에 가장 아래쪽에 있는 점을 하나 선택합니다. 그리고 이 점을 기준으로 다른 점들에 선을 그어 각도 순으로 정렬합니다. 각도가 같을때는 거리가 가까운 것을 우선시합니다.

 이렇게 정렬된 값을 기준으로 차례대로, ccw를 이용해 ccw가 맞으면 스택에 추가해주고, ccs가 아니면, ccw가 될때까지 스택에 넣어둔 값을 빼줍니다. 이유는 Convex Hull 자체가 전체를 내부에 두는 다각형이니 만큼 오목 다각형이 될 수는 없기 때문입니다. 이 문제를 시계방향으로 정렬하고, cw인지 계속 판별해서 풀 수도 있겠지만, 우선 ccw로 정하고 나서 계속 구해나가다가 cw가 발견되면 이전 점들과 현재 점을 이었을 때도 ccw가 되도록 처리하는 것입니다.

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;

public class ConvexHull {
	
	public static int N = 0;
	
	public static Point[] points = null;
	
	public static class Point {
		
		long x = 0;
		long y = 0;
		
		public Point(long x, long y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static long ccw (Point a, Point b, Point c) {
		
		long outPd = outProduct(new Point(b.x - a.x, b.y - a.y), new Point(c.x - a.x, c.y - a.y));
		if (outPd > 0)		return 1;
		if (outPd < 0)		return -1;
		else				return 0;
	}
	
	public static long outProduct (Point a, Point b) {
		return a.x * b.y - a.y * b.x;
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		points = new Point[N];
		
		long x = 0;
		long y = 0;
		StringTokenizer st = null;
		for (int i = 0 ; i < N ; i++) {
			
			st = new StringTokenizer(br.readLine());
			x = Long.parseLong(st.nextToken());
			y = Long.parseLong(st.nextToken());
			
			points[i] = new Point(x, y);
			
			// 더 y축으로 아래쪽에 위치한 좌표가 있으면, 해당 값을 0번 값으로 변경해준다.
			if (i != 0 && points[0].y > points[i].y || (points[0].y == points[i].y && points[0].x > points[i].x)) {
				Point temp = points[0];
				points[0] = points[i];
				points[i] = temp;
			}
		}
		
		for (int i = 1 ; i < N ; i++){
			points[i].x -= points[0].x;
			points[i].y -= points[0].y;
		}
		points[0] = new Point(0, 0);

		Arrays.sort(points, 1, N, new Comparator<Point>(){

			@Override
			public int compare(Point a, Point b) {
				
				long ccw = ccw(points[0], a, b);
				if(ccw > 0)	return -1;
				if(ccw < 0) return 1;
				else {
					
					long dist = ((long)Math.abs(a.x) + (long)Math.abs(a.y)) - ((long)Math.abs(b.x) + (long)Math.abs(b.y));
					if (dist > 0) return 1;
					if (dist < 0) return -1;
					return 0;
				}
			}
		});
		
		Stack<Integer> stk = new Stack<>();		// Index 만 넣는다.
		stk.add(0);
		for (int i = 1 ; i < N ; i++) {
			
			while (stk.size() > 1 && ccw(points[stk.get(stk.size()-2)], points[stk.get(stk.size()-1)], points[i]) <= 0) {
				
				stk.remove(stk.size()-1);
			}
			stk.add(i);
		}
		
		bw.write("" + stk.size());
		bw.flush();
		bw.close();
	}
}