문제 66
볼록 껍질
평면 위에 $N$개의 점이 있다. 모든 점을 포함하는 볼록 껍질을 이루는 꼭짓점의 개수를 출력하라.
볼록 껍질의 한 변 위에 있는 점은 꼭짓점으로 세지 않는다.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(3 \le N \le 200\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 점의 좌표를 의미하는 두 정수 $x$, $y$가 공백으로 구분되어 주어진다. $(-10^9 \le x, y \le 10^9)$
같은 좌표를 가진 점은 두 번 이상 주어지지 않으며 한 직선 위에 있지 않은 세 점이 존재한다.
출력
볼록 껍질을 이루는 꼭짓점의 개수를 출력한다.
예제 입력 1
8 0 0 2 0 4 0 4 2 4 4 2 4 0 4 2 2
예제 출력 1
4
공식 해설
점들을 $(x,y)$의 사전 순으로 정렬한 뒤 아래쪽 껍질과 위쪽 껍질을 따로 만드는 Monotone Chain을 사용한다.
아래쪽 껍질은 점을 정렬 순서대로 스택에 넣으며 만든다. 스택의 마지막 두 점과 새 점이 반시계 방향을 이루지 않으면 가운데 점을 제거한다. 반시계 방향이 될 때까지 제거한 뒤 새 점을 넣는다.
시계 방향으로 꺾이는 가운데 점은 바깥쪽 볼록 경계에 필요하지 않다. 외적이 $0$인 점도 제거하면 한 변의 중간에 놓인 점을 꼭짓점에서 제외할 수 있다. 같은 과정을 역순으로 수행하면 위쪽 껍질을 얻는다.
두 껍질을 합칠 때 맨 왼쪽과 맨 오른쪽 끝점은 양쪽에 들어 있으므로 각각 한 번만 포함한다. 문제에서 일직선이 아닌 세 점이 보장되므로 이렇게 얻은 다각형의 꼭짓점 수를 출력하면 된다.
각 점은 각 스택에 한 번 들어가고 최대 한 번 나온다. 따라서 정렬을 포함한 시간복잡도는 $O(N\log N)$, 공간복잡도는 $O(N)$이다. 변 위의 점을 정확히 제외할 수 있도록 외적의 부호와 $0$ 여부를 정수로 판정한다.
구현 · 언어별 풀이
C++ 구현
점은 pair<long long, long long>으로 저장해 sort한다. 껍질은 vector를 스택처럼 사용하고 외적이 $0$ 이하인 동안 pop_back()한다. 외적은 long long으로 계산하며 두 껍질을 합칠 때 공통 끝점을 한 번씩 제외한다.
C 구현
점 구조체 배열을 x,y 순으로 qsort하고 hull 배열의 뒤에서 CCW가 0 이하인 점을 제거한다. 좌표와 외적은 long long이며 비교 함수는 x 차를 int로 잘라 반환하지 않는다.
Python 구현
(x,y) 튜플을 sort()하고 hull 리스트를 스택처럼 사용한다. ccw <= 0인 마지막 점을 pop하여 변 위의 중간 점을 제외한다. Python int 외적으로 정확한 방향을 판정한다.
Java 구현
점을 좌표 순으로 정렬하고 hull을 배열 스택에 저장한다. 좌표 차·외적은 long으로 계산한다. comparator와 CCW를 분리하고 실수 각도 정렬은 사용하지 않는다.
Rust 구현
(i64,i64) 튜플을 sort_unstable()하고 Vec hull에서 ccw <= 0인 점을 pop한다. 상·하단 hull을 합칠 때 두 끝점을 중복 출력하지 않는다.
JavaScript 구현
좌표는 Number로 보관하고 $x$, 그다음 $y$의 숫자 비교로 정렬한다. 문자열 기본 정렬은 좌표의 숫자 순서를 보장하지 않는다.
회전 방향은 좌표 차를 BigInt로 바꾼 뒤 외적을 계산한다. 좌표가 $10^9$ 수준이면 곱이 안전 정수 범위를 넘어, 부동소수 외적에 epsilon을 넣는 방법으로 정확한 정수 판정을 대신할 수 없다.
아래·위 껍질을 만들 때 외적이 $0$ 이하이면 마지막 점을 제거한다. 이 문제는 변 위에 놓인 내부 점이 아니라 꼭짓점 개수를 묻기 때문이다. 각 껍질의 양 끝점을 중복 세지 않도록 길이 합에서 $2$를 뺀다. 껍질은 배열의 push·pop으로 관리하면 충분하다.