> Convex Hull(볼록 껍질)
볼록 껍질(convex hull)이라는 개념은 2차원 평면상에 점이 여러 개가 있을 때 이 점들 중 일부를 골라서 만들 수 있는, 나머지 점들을 모두 포함하는 볼록다각형을 말합니다.
이때 포함한다는 말은 점이 다각형의 경계에 걸쳐 있는 것도 인정합니다. 즉, 변 위에 있어도 된다는 것.
이런 점들이 있다면,
이것이 바로 볼록 껍질입니다. 볼록 껍질에 속한 점 개수는 6개군요.
그럼 이러한 다각형이 왜 항상 볼록다각형으로 결정될 수 있을까요? 사실 그건 조금만 생각해 보면 직관적으로 당연합니다.
점을 모두 포함하는 어떤 오목다각형이 있다고 해도, 오목한 지점의 점을 다각형에서 제외시키고 전후의 점을 그냥 이어버려도 새 다각형에 그 점도 포함이 되니까요.
또한, 볼록다각형에 한해서 각종 기하 관련 소문제를 쉽게 풀 수 있는 경우가 많기 때문에 특히나 볼록다각형이란 점이 중요합니다.
간혹 이렇게 볼록다각형이 아니라 그냥 점(점이 하나였을 경우)이나 선(모든 점이 일직선상에 놓여 있음)의 형태가 나오기도 합니다. 그래도 보통은 큰 지장이 없긴 합니다.
그러나 분명히 이런 trivial한 경우를 예외처리해 주어야 하는 상황이 있긴 합니다.
- BOJ[1708] : 볼록 껍질
https://www.acmicpc.net/problem/1708
[
1708번: 볼록 껍질
첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x��
](https://www.acmicpc.net/problem/1708)
보통 볼록 껍질을 추출하는 데는 이 문제와 같이 N개 점에 대해 최소 O(NlogN)의 시간복잡도를 요합니다.
이 시간복잡도를 만족하는 대표적인 알고리즘이 바로 그라함 스캔(Graham's scan)입니다.
스택이 필요합니다. 점 하나를 기준으로 뽑아서 그 점 기준으로 시계방향 혹은 반시계방향으로 나머지 점들을 훑어가며 볼록 껍질에의 포함여부를 결정하는 방법입니다.
그림을 새로 그리기가 매우 귀찮으므로 전에 사용했던 그림을 그대로 써야겠습니다.
이러한 점들이 널려 있다고 할 때, 그라함 스캔을 사용하여 볼록 껍질을 추출해 봅시다.
먼저 기준점을 잡습니다. 그 방향은 아무 상관이 없긴 한데, 해당 점을 지나는 어떤 직선을 그었을 때 다른 모든 점이 직선을 기준으로 한쪽에만 위치해 있어야 합니다(직선 위에는 있어도 됩니다).
보통은 x좌표가 가장 작거나, y좌표가 가장 작거나... 이런 점들을 선택합니다.
그리고 그 기준점을 기준으로 하여 다른 점들을 시계방향 혹은 반시계방향으로 정렬한 후 순서대로 훑을 겁니다.
이 정렬하는 시간이 O(NlogN)일 테죠. 그리고 보통 각도값이 커지는 방향인 반시계방향을 사용합니다.
먼저 스택에 0번 점과 1번 점을 순서대로 넣고 시작합니다.
이제부터 나머지 2~6번 점들을 순서대로 훑으면서 스택에 볼록 껍질에 해당하는 점만을 순서대로 남겨놓을 겁니다.
이제부터 스택 제일 위의 점 2개가 이루는 직선을 기준으로 점들이 항상 한쪽 방향에만 나타나게 해야 합니다.
이 방향은 벡터의 방향에 따라 결정되어야 하는데요, 지금 우리의 경우는 벡터가 위를 향한다면 직선의 왼쪽에 있게 하는 겁니다. 그냥 편하게 이제부터 왼쪽/오른쪽에 있다고 표현하겠습니다.
먼저 2번 점은 직선 01에 대해 왼쪽에 있으므로 스택에 넣습니다.
그 다음, 3번 점 또한 직선 12에 대해 왼쪽에 있으므로 스택에 넣습니다.
그 다음, 4번 점 또한 직선 23에 대해 왼쪽에 있으므로 스택에 넣습니다.
그런데 지금 딱 봐도 4번 점은 컨벡스 헐에 절대 없을 것 같은데요... 일단 봅시다.
점 5번이... 직선 34에 대해 오른쪽에 있습니다.
이때는 스택에서 제일 위에 있는 4번 점을 빼버려야 합니다. 이렇게 해서 컨벡스 헐 안쪽 점들을 걸러냅니다.
그 다음, 지금 스택의 제일 위인 점 2개로 이루어지는 직선 23에 대해서는
5번 점이 왼쪽에 있으므로, 5번 점은 그대로 스택에 쌓습니다.
물론, 한 번에 연속해서 여러 개의 점이 스택에서 빠져나가는 경우도 충분히 발생하며, 계속 빠져나가다가 스택에 점이 2개만 남게 되면 멈춥니다.
점 6번도 넣습니다.
6번 점이 마지막이므로 컨벡스 헐 추출이 끝난 겁니다.
컨벡스 헐은 스택의 바닥부터 순서대로 0-1-2-3-5-6번 점이 이루게 되는데, 사실 위부터 읽어도 다각형인 건 맞죠. 점을 훑는 순서만 반대일 뿐.
이때, 도중에 직선 위에 다음 점이 있을 수도 있는데요. 보통 이때도 가운데의 점을 빼버립니다.
컨벡스 헐의 연속한 세 개 점이 일직선상에 있다면 가운데 점이 빠져도 형태도 유지되고, 가운데 점이 가지는 의미가 거의 없기 때문.
이제 소스 코드를 봅시다.
#include <cstdio>
#include <cmath>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX = 100000;
struct Point{
int x, y; // 실제 위치
int p, q; // 기준점으로부터의 상대 위치
Point(): Point(0, 0, 1, 0){}
Point(int x1, int y1): Point(x1, y1, 1, 0){}
Point(int x1, int y1, int p1, int q1): x(x1), y(y1), p(p1), q(q1){}
// p, q 값을 기준으로 정렬하기 위한 관계연산자
bool operator <(const Point& O){
if(1LL*q*O.p != 1LL*p*O.q) return 1LL*q*O.p < 1LL*p*O.q;
if(y != O.y) return y < O.y;
return x < O.x;
}
};
// 벡터 AB와 벡터 AC의 CW/CCW
long long ccw(const Point& A, const Point& B, const Point& C){
return 1LL*(B.x-A.x)*(C.y-A.y) - 1LL*(B.y-A.y)*(C.x-A.x);
}
int main(){
int N;
scanf("%d", &N);
Point p[MAX];
for(int i=0; i<N; i++){
int x, y;
scanf("%d %d", &x, &y);
p[i] = Point(x, y);
}
// 점들을 y좌표 -> x좌표 순으로 정렬: 0번 점이 제일 아래 제일 왼쪽
sort(p, p+N);
for(int i=1; i<N; i++){
p[i].p = p[i].x - p[0].x;
p[i].q = p[i].y - p[0].y;
}
// 0번을 제외한 점들을 반시계 방향으로 정렬
sort(p+1, p+N);
stack<int> S;
// 스택에 처음 2개의 점을 넣음
S.push(0);
S.push(1);
int next = 2;
// 모든 점을 훑음
while(next < N){
// 스택에 2개 이상의 점이 남아있는 한...
while(S.size() >= 2){
int first, second;
first = S.top();
S.pop();
second = S.top();
// 스택 최상단 점 2개와 다음 점의 관계가 CCW일 때까지 스택 pop
if(ccw(p[second], p[first], p[next]) > 0){
S.push(first);
break;
}
}
// 다음 점을 스택에 넣음
S.push(next++);
}
// 이제 스택에 컨벡스 헐 정점들이 순서대로 쌓여 있음
// 컨벡스 헐의 점 개수 출력
printf("%d\n", S.size());
}0번 점을 제일 아래의, 만약 제일 아래인 점이 여러 개면 그 중 제일 왼쪽 점으로 고르고
나머지 점들을 0번 점 기준으로 반시계 방향으로 정렬합니다.
그리고 점들을 훑으면서 컨벡스 헐을 추출합니다.
그럼 볼록 껍질로 할 수 있는 게 뭐가 있는지 살펴봅시다.
- BOJ[2254] : 감옥 건설
https://www.acmicpc.net/problem/2254
[
2254번: 감옥 건설
첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.
](https://www.acmicpc.net/problem/2254)
담이 볼록다각형 모양이고 담이 중첩되어야 하므로,
이 문제에서 구해야 하는 것은 (Px, Py)를 포함하는 중첩된 최대 볼록 껍질 개수입니다.
예제를 나타내면 이렇게 됩니다.
이 문제를 풀려면 다음과 같은 과정을 반복하면 되겠죠.
① 볼록 껍질을 추출하고, 볼록 껍질 위의 점들을 담 기둥 집합에서 제외한다.
② 이번 볼록 껍질 안에 감옥이 포함된다면 볼록 껍질 크기(점 개수)를 더한 후 ①로 돌아간다.
③ 그렇지 않다면 종료한다.
이때, 볼록다각형 안에 점이 존재하는지를 판별하는 방법 또한 CCW를 사용하는데요.
판별하고 싶은 점이 O일 때, 볼록다각형 상의 모든 연속된 두 점 P, Q에 대해
벡터 OP와 벡터 OQ의 CW/CCW 여부가 전부 같으면 점 O는 볼록다각형 내부에, 아니라면 외부에 있습니다.
- BOJ[7420] : 맹독방벽
https://www.acmicpc.net/problem/7420
[
7420번: 맹독 방벽
첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 젖ㅇ수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 ��
](https://www.acmicpc.net/problem/7420)
뭔가 느낌이 볼록 껍질이긴 한데 모든 정점들로부터 거리 L을 유지해야만 한다네요.
일단 거리 L = 0이라 생각해 봅시다. 그렇다면 방벽은 완벽하게 볼록 껍질의 형태가 됩니다.
L이 양수일 때, 방벽은 볼록 다각형을 감싼 형태인데 모서리 부분은 둥글어지게 되는 모양새를 띄게 됩니다.
빨간색이 컨벡스 헐이고 주황색이 방벽인데요. 대략 어떤 형태인지 짐작이 가실 겁니다.
이제 방벽의 둘레의 길이를 구하면 되는 것이죠.
일단 곡선이 아닌 부분의 총합은 컨벡스 헐의 모서리 길이 총합과 같을 것이고요,
모서리의 둥근 부분인 곡선 길이 합을 따로 더해서 거기다 더하면 되겠습니다.
부채꼴의 곡선 모서리 길이를 구할 때 옆선 길이에 각도를 곱한다는 공식에서
다음과 같은 방식으로 곡선 부분의 길이를 구할 수 있습니다.
- BOJ[3878] : 점 분리
https://www.acmicpc.net/problem/3878
[
3878번: 점 분리
평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹
](https://www.acmicpc.net/problem/3878)
상당히 어려운 문제입니다. 컨벡스 헐을 사용해야 한다는 것을 알기 전에는요.
이 문제를 컨벡스 헐로 풀려고 생각한다면, 해답은 이렇습니다.
두 집단의 정점들로 각각 볼록 껍질을 만들었을 때, 둘이 만나지 않으면 분리 가능하다.
이제 가능 여부는 직선으로 이 두 볼록다각형을 나눌 수 있느냐로 바뀌게 되죠.
허허... 대단하죠? 물론, 모서리만 겹쳐도 안 됩니다. 문제에서 직선이 어떤 점과도 만나면 안 된다고 했기 때문이죠.
볼록다각형 두 개가 겹쳐있는지 판별하려면 위의 볼록다각형의 점 포함 여부를 응용하면 됩니다.
한쪽 볼록다각형의 모든 점에 대해 상대 볼록다각형 안에 속해 있는지 판단해보고, 하나라도 속하면 두 볼록다각형은 겹치는 겁니다. 그런데 이걸로 끝은 아니고, 양 볼록다각형의 선분들끼리도 겹치는지 확인해줘야 합니다.
설명을 보면 알겠지만 솔루션이 꽤 명쾌한 데 반해 구현하기는 무진장 어렵습니다...
- BOJ[9240] : 로버트 후드
https://www.acmicpc.net/problem/9240
[
9240번: 로버트 후드
첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다.
](https://www.acmicpc.net/problem/9240)
글의 내용을 좀 추가하겠습니다. 볼록 껍질의 대표적인 문제 중 하나가 제일 멀리 떨어져 있는 두 점 구하기입니다.
제일 멀리 떨어져 있는 점들은 반드시 볼록 껍질 위에 존재한다는 것이 핵심입니다.
만약 볼록 껍질상에 존재하지 않는 점이 한 개 이상 최장 거리 점 쌍에 포함된다고 해봅시다.
위 두 개의 점이 그 쌍이라고 해보죠. 위에 있는 점이 볼록 껍질에 포함이 안 됩니다.
그러면 저렇게 그 점에 제일 가까운 두 볼록 껍질상의 점들이 오히려 진짜 최장 거리 점 쌍의 후보가 됩니다. 저렇게 반대편 점과 이어보면 직관적으로 길이가 더 길다는 걸 알 수 있습니다.
그러므로 볼록 껍질 위에 있는 두 점 쌍에 대해 거리를 모두 거해 보고 제일 긴 것을 뽑으면 되는데... 모든 점이 볼록 껍질 위에 속해 있으면 O(C^2)로 시간 초과가 날 것 같습니다.
다행히도, 이 문제의 경우 주어지는 점들의 좌표 값 범위가 그렇게 크지 않기 때문에 저 정도로 많은 점이 다 볼록 껍질 위에 살아남지 못해서 저 방법이 먹힙니다.
그러나 점 N개로 이루어진 볼록 껍질이 주어졌을 때 O(N)의 시간에 볼록 껍질 상의 최장 거리 점 쌍을 구해내는 테크닉이 존재하는데, 회전하는 캘리퍼스(roataing caplipers) 테크닉이라고 합니다.
처음에 직선의 방향을 정해두고, 두 평행한 직선으로 볼록 껍질을 양쪽에서 에워쌉니다.
여기서 볼록 껍질을 시계 방향이나 반시계 방향 중 한 방향으로 고정시켜서 계속 회전해 가면서 매번 두 직선과 맞닿은 점 사이의 거리를 구해봅니다.
처음에는 아무 두 점이나 뽑아서 거리를 구해 보고 시작합니다.
우리는 직선들을 반시계 방향으로 회전시킨다고 정하겠습니다.
이때 직선을 얼마나 회전시킬지가 문제입니다. 두 직선을 회전시키다가 볼록 껍질의 한 변에 닿는 순간 멈추는 겁니다. 그 결과, 저렇게 두 개의 각도 중 작은 각 쪽의 변이 먼저 닿게 됩니다.
여기서 평행한 직선과 닿은 변에서, 원래 직선과 닿아있던 점이 그 변의 반대편 점으로 옮겨갑니다. 그리고 다시 거리를 잽니다. 그 뒤 다시 회전을 합니다. 이번엔 아래쪽 각도가 더 작아서 저쪽 변이 먼저 접하게 됩니다.
다음 회전을 하고 새 선분의 거리를 잰 후, 또 회전합니다.
계속 회전을 하다가, 한 번 봤던 회전 각도나 거기서 180도 더 회전한 모양으로 볼록 껍질이 놓여있게 되면 탐색을 종료해도 됩니다.
그리고 더 간단히는 회전을 N번만 행해도 그 안에 반드시 최장거리 점 쌍을 한 번은 보게 됩니다. 이 부분은 바로 와닿지 않는데, 나중에 내용을 추가하도록 하겠습니다. 아무튼 따라서 회전하는 캘리퍼스 파트는 O(N)의 시간 안에 해결됩니다.
문제는 대체 이걸 어떻게 구현하느냐인데, 말로 하면 쉽지 되게 막막합니다.
제일 문제인 부분은 양쪽 점 중 어느 쪽이 다음 점으로 옮겨가는지를 정하는 부분인데, 일단 테스트 케이스가 빡세지 않았다면 현재 직선의 벡터를 보관해 두면서 각 점마다 다음 점으로 향하는 벡터와 각각 이루는 각도나 cos 값을 구해서(대표적으로 내적을 사용하는 방법이 있습니다) 방향을 정하는 것도 충분히 가능한데, 현재는 실수 오차를 반드시 잡아내려는 악의적인(?) 데이터가 많은 추세라...
요지는 현재 직선의 벡터와, 위에서 말한 두 벡터가 각각 이루는 각도 중 작은 걸 찾아내야 합니다. 이걸 벡터의 외적으로 해결할 수 있습니다.
https://en.wikipedia.org/wiki/Cross_product
[
Cross product - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Mathematical operation on two vectors in three-dimensional space In mathematics, the cross product or vector product (occasionally directed area product, to emphasize its geometric sig
en.wikipedia.org
](https://en.wikipedia.org/wiki/Cross_product)
위키를 참고하면, 두 벡터를 서로 외적해서 나오는 값의 부호를 보고 어느 벡터가 더 기준벡터에 가까운지, 즉 각도가 더 작은지를 알 수 있습니다.
현재 이 상황이라고 해 봅시다. 이때 저렇게 두 개의 벡터와 평행선이 이루는 각도를 비교해야 하는 것인데,
아래쪽 벡터를 이렇게 위로 옮겨오고 위쪽 벡터의 방향을 뒤집어 점을 공유하게 만들어보면, 이 상태에서 평행선의 벡터가 축 벡터라 치고 두 벡터를 외적해서 부호를 보고 어느 벡터가 더 작은 각도를 가지는지 판단할 수 있습니다.
지금까지 대표적인 문제 몇 개를 살펴보았는데, 사실 기하 관련 문제는 대부분 구현이 정말 어렵고요,
특히 기하 관련 문제는 거의 항상 trivial case에 대한 예외 처리를 해주어야 해서 더욱 틀릴 위험이 높습니다.
또한 문제가 무엇을 묻느냐에 따라 점이 컨벡스 헐 경계에 걸쳐도 되고, 걸쳐선 안 될 수도 있으며... 여튼 문제에 따라 고려하고 고쳐야 할 게 많은 편입니다.
볼록 껍질 관련 추쳔 문제
1708번: 볼록 껍질
한번 뽑아봅시다.
6850번: Cows
컨벡스 헐의 면적을 구하라네요. 볼록다각형의 면적 구할 줄 아시죠?
17403번: 가장 높고 넓은 성
감옥 건설 문제의 열화판입니다. 매번 볼록 껍질을 찾아다 층을 건설해 나가면 됩니다. 어떻게 보면 그리디 알고리즘이라고도 할 수 있습니다. 점이 2개 이하로 남거나, 점 3개 이상의 볼록 껍질을 만들 수 없게 되는 시점에서 종료하면 됩니다.
2번 예제를 보면 아시겠지만, 볼록 껍질상의 세 점이 한 직선을 지나면 안 됩니다. 본문의 코드를 사용하면 문제 없겠지만요.
2254번: 감옥 건설 (★)
위에서 설명한 문제입니다.
7420번: 맹독 방벽
위에서 설명한 문제입니다.
3878번: 점 분리 (★)
위에서 설명한 문제입니다.
9240번: 로버트 후드 (★)
위에서 설명한 문제입니다.
10254번: 고속도로 (★)
로버트 후드 문제의 상급 난이도 버전으로, 좌표값의 범위가 넓어서 이제 반드시 O(N) 회전하는 캘리퍼스 테크닉을 사용해야 합니다.
'알고리즘 > [ 개념 ]' 카테고리의 다른 글
| [ 개념 ] 47. 스위핑 알고리즘(Sweeping Algorithm) (0) | 2020.09.22 |
|---|---|
| [ 개념 ] 46. 레이지 프로퍼게이션(Lazy Propagation) (0) | 2020.09.22 |
| [ 개념 ] 44. 이분 매칭(Bipartite Matching) (2) | 2020.09.17 |
| [ 개념 ] 43. 네트워크 유량(Network Flow) (6) | 2020.09.16 |
| [ 개념 ] 42. 오일러 경로, 오일러 회로 (0) | 2020.09.16 |