일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- Implementation
- IOI 2013
- Manacher 알고리즘
- BAPC 2018
- ICPC 연습
- convex hull
- Z 알고리즘
- JOI
- 8192
- 기하 알고리즘
- 세그먼트 트리
- 볼록 껍질
- codeforces
- 그래프
- acmicpc.net
- 백준 온라인 저지
- BAPC
- 2794
- 14179
- Divide and conquer optimization
- 기하
- boj
- 컨벡스 헐
- JOI 2018
- 코드포스
- Manacher's algorithm
- Z algorithm
- 구현
- DP
- POI Solution
- Today
- Total
프로그래밍 연습장
Graham Scan 본문
2차원 좌표평면에 점들이 있을 때, 이들의 컨벡스 헐은 점들을 모두 포함하는 가장 작은 볼록다각형을 뜻한다. "점들이 있는 곳에 못을 박고, 바깥에 엄청 큰 고무줄을 놓았을 때 고무줄이 걸리는 점들"이라는 비유가 좋다. 꼭짓점이 점들의 부분집합이고, 모든 점을 포함하는 볼록다각형이면 컨벡스 헐이다.
컨벡스 헐, 정확히 "컨벡스 헐의 꼭짓점에 위치한 점들의 리스트"을 구하는 Graham Scan 알고리즘은 구현이 길지 않다:
1
2
3
4
5
6
7
8
9
|
sort(a, a+n);
sort(a+1, a+n, [](pint x, pint y) { return ccw(a[0], x, y) > 0 or (ccw(a[0], x, y) == 0 and dist(a[0], x) < dist(a[0], y)); });
t = 2;
for (int i=2; i<n; i++) {
while (t>1 and ccw(r[t-2], r[t-1], a[i]) <= 0) t--;
r[t++] = a[i];
}
|
cs |
다음은 이 알고리즘의 동작 원리를 설명하는 세 줄 요약..이라기 보다는 이 세 줄이 전부다.
-
점들을 좌표 순서대로 정렬했을 때의 첫 정점은 무조건 컨벡스 헐의 꼭짓점을 이룬다. 즉, X좌표가 가장 작은 점들 중 Y좌표가 가장 작은 점을 찾아, 얘를 극점이라고 하자. 극점은 컨벡스 헐의 꼭짓점에 포함된다.
-
나머지 $N-1$개의 점들을 극점에서 시작하는 벡터가 축과 이루는 각도 순으로 정렬한다. 각도가 같다면 2순위로 극점과의 거리의 오름차순이 되게 하자.
-
정렬한 순서대로 $N-1$개의 점들을 차례로 보면서, 컨벡스 헐의 꼭짓점 리스트에 넣는다. 무조건 넣는다. 만약 새로운 점을 추가할 때 컨벡스 헐에 오목한 각이 생겨서 못 넣는다면, 오목한 각이 없어질 때까지 마지막으로 추가한 점들을 계속 빼서라도 기어코 넣는다.
일종의 그리디 알고리즘인데, 올바르게 작동함은 다음과 같이 증명한다. 말장난 같다.
-
수학적 귀납법을 쓰자. 극점을 $p_1$, 나머지 점을 각도 순으로 $p_{2..n}$이라 하자. $p_{1..i}$의 컨벡스 헐을 $C_i$라 하자. 물론 $S(C_1) = 0$임은 당연하다.
-
Graham Scan 알고리즘으로 $C_{i-1}$까지를 올바르게 구했다고 하자. 이제 $C_i$를 구성하기 위해 $p_i$를 추가하려 한다. $p_i$는 $C_{i-1}$에 없으니까, $C_i$의 꼭짓점에 포함되어야 한다.
-
$C_{i-1}$에다 $p_i$를 더해 다각형을 만들었는데, $p_i$와 직전에 추가한 두 점이 이루는 각 빼곤 다 볼록함을 알고 있다. 만약 새로 생긴 각이 오목하다면, 직전에 추가한 점을 제거해도 모든 점을 아직 포함하고 있다. 그 과정을 반복하다 보면 볼록해지고, 컨벡스 헐이 되고, $C_i$가 된다.
그리고 구현할 때 기억할 점. 기하 알고리즘이 다 그렇듯이 이상한 곳에서 뻑나기 십상이다.
1. 문제에서 한 직선 위에 여러 점이 있을 수 없다는 조건을 주지 않는 이상, 무조건 거리의 오름차순으로 정렬해야 한다. 까먹어도 대부분의 경우엔 상관 없지만, 첫 번째로 추가하는 점이 극점과 이루는 직선에 여러 점이 있을 때 오작동할 수 있다.
2. 위 6번 줄의 ccw 조건에서 등호를 빼면 180'의 내각을 이루는 꼭짓점도 모두 포함하게 된다. 즉 컨벡스 헐의 경계 위에 있는 모든 점을 구할 수 있게 된다. 문제에 따라서 알아서 쓰면 된다. 하지만 이 때에는 이 후처리를 잊으면 안 된다.
-
마지막 점($P_n$)이 극점($P_1$)과 이루는 직선 위의 점들은 거리가 감소하는 순서대로 추가되어야 한다. 따라서 모두 추가된 뒤에 이 점들의 순서를 뒤집는 처리를 해야 옳은 순서가 된다.
이를 포함한 "컨벡스 헐 위의 경계 위에 있는 모든 점을 구하는" 코드는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
sort(a, a+n);
sort(a+1, a+n, [](pint x, pint y) { return ccw(a[0], x, y) > 0 or (ccw(a[0], x, y) == 0 and dist(a[0], x) < dist(a[0], y)); });
for (int i=n-1; i; i--) if (ccw(a[0], a[i], a[i-1])) {
reverse(a+i, a+n);
break;
}
t = 2;
for (int i=2; i<n; i++) {
while (t>1 and ccw(r[t-2], r[t-1], a[i]) < 0) t--;
r[t++] = a[i];
}
|
cs |
3. ccw 함수
1
2
3
4
5
6
7
|
int ccw(pint a, pint b, pint c) {
lint k = a.x * (lint)b.y + b.x * (lint)c.y + c.x * (lint)a.y
-a.y * (lint)b.x - b.y * (lint)c.x - c.y * (lint)a.x;
if (k>0) return 1;
if (k<0) return -1;
return 0;
}
|
cs |
에서 정수 오버플로우가 나지 않게 64비트 정수형으로 캐스팅해주자. 그냥 좌표 자체를 처음부터 넉넉하게 64비트로 선언하는 게 제일 편하다.
'알고리즘' 카테고리의 다른 글
Manacher의 알고리즘과 Z 알고리즘 (0) | 2018.02.27 |
---|---|
그래프의 간선 리스트 표현 (2) | 2017.12.06 |
Heavy Light Decomposition의 구현 (0) | 2017.12.03 |
배열을 이용한 Persistent Segment Tree의 구현 (0) | 2017.10.08 |
좌표평면에서 가장 먼 점 찾기 (2) | 2017.09.08 |