이 포스트는 회전하는 캘리퍼스 알고리즘(Rotating Calipers)에 대해 다루고, 이에 대한 예제를 풀어보면서 알고리즘을 직접 코드로 구현하는 내용을 다루고 있습니다.
풀이할 예제는 프로그래밍 문제 사이트 백준 Online Judge의 8927번 : 'Squares'이며, 문제의 난이도는 Solved.ac 기준 Platinum II에 해당합니다.
우리는 Convex Hull 알고리즘을 사용하면 주어진 점들 중에서 가장 외곽의 점들을 선택하여 볼록다각형을 구성할 수 있고, 이는 주어진 점들로 구성할 수 있는 최대 면적이 됩니다.
그렇다면 주어진 점들 중에서 가장 긴 거리를 구하는 방법은 무엇일까요?
가장 간단하게 완전 탐색으로 생각해보면, 점의 개수가 N개라고 할 때 이들 중 2개를 이루는 점의 쌍을 모두 선택해서 확인해보면 되므로 O(N^2) 시간이 걸릴 것입니다.
만약 점의 수가 10만개를 넘어간다면 O(N^2) 알고리즘으로는 시간 초과에 걸리게 됩니다.
그러나 '회전하는 캘리퍼스' 알고리즘을 사용하면 O(N) 시간에 최장 거리의 두 점을 탐색할 수 있습니다.
이에 대한 아주 적절한 예시 문제를 풀이하면서 설명해보도록 하겠습니다.
8927번 : Squares
8927번: Squares
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains an integer, n , the number of squares, where 2 ≤ n ≤ 100,000
www.acmicpc.net
↑ 문제 링크는 여기에 첨부해두었으니, 먼저 풀어보시면서 생각해보는 것도 좋습니다.
문제를 해석해보면 정사각형의 왼쪽 아래 점들과, 각 정사각형의 한 변의 길이가 주어졌을 때, 최장 거리 두 점 사이의 거리의 제곱을 구하는 문제입니다.
백준에서 6명밖에 안 푼 문제인데 제가 직접 풀이했다는 것을 보여주기 좋은 문제다 싶어서 갖고 왔습니다.
풀이를 생각해보면, 먼저 Convex Hull 알고리즘을 사용하여 가장 외곽의 점들을 선택해줍니다.
그 다음에 양 끝 점 2개를 잡고 거리를 구한 뒤, 반시계 방향으로 돌아가면서 더 작은 각도에 있는 점으로 끝 점을 바꿔주고 거리를 측정하는 과정을 반복합니다.
이 때 거리가 최댓값을 넘는다면 이를 갱신해줍니다.
이처럼 더 작은 각도에 존재하는 다음 점으로 넘어가면서, 두 점 사이의 거리를 구하는 알고리즘이 '회전하는 캘리퍼스' 알고리즘입니다.
가끔 최대 직경이 왜 볼록다각형 꼭짓점 상의 두 점인지 모르겠다는 사람들이 있는데, 이는 귀류법으로 쉽게 증명됩니다.
만약 외부 점이 아닌 볼록다각형 내부의 점이 최대 직경이 된다고 가정하면, 두 점을 반지름으로 원을 그렸을 때 볼록다각형과 만나게되므로 모순이 발생합니다.
어쨌든 이 알고리즘을 어떻게 구현하면 되는지 제가 코드를 짜왔습니다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct Coor { long long x, y; };
Coor operator-(Coor a, Coor b) {
Coor c;
c.x = a.x - b.x;
c.y = a.y - b.y;
return c;
}
vector<Coor> Point;
double Abs(double a) { return a>=0?a:-a; }
long long CCW(Coor a, Coor b, Coor c) { return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y); }
int DistSq(Coor a, Coor b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }
bool minCCW(Coor a, Coor b) {
long long Value = CCW(Point[0], a, b);
if(Value != 0) return Value > 0;
else if(a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int main() {
int T, N;
scanf("%d", &T);
for(int t=0; t<T; t++) {
scanf("%d", &N);
Point.resize(N*4);
for(int i=0; i<N; i++) {
long long xCorner, yCorner, w;
scanf("%lld %lld %lld", &xCorner, &yCorner, &w);
Point[i*4].x = xCorner, Point[i*4].y = yCorner;
Point[i*4+1].x = xCorner+w, Point[i*4+1].y = yCorner;
Point[i*4+2].x = xCorner, Point[i*4+2].y = yCorner+w;
Point[i*4+3].x = xCorner+w, Point[i*4+3].y = yCorner+w;
}
for(int i=1; i<N*4; i++) {
if(Point[i].y < Point[0].y || (Point[i].y == Point[0].y && Point[i].x < Point[0].x)) {
long long temp = Point[0].x;
Point[0].x = Point[i].x;
Point[i].x = temp;
temp = Point[0].y;
Point[0].y = Point[i].y;
Point[i].y = temp;
}
}
sort(Point.begin()+1, Point.end(), minCCW);
stack<Coor> Convex;
Coor Temp1, Temp2, First;
Convex.push(Point[0]);
Convex.push(Point[1]);
for(int i=2; i<N*4; i++) {
while(Convex.size() >= 2) {
Temp2 = Convex.top();
Convex.pop();
Temp1 = Convex.top();
if(CCW(Temp1, Temp2, Point[i]) > 0) {
Convex.push(Temp2);
break;
}
}
Convex.push(Point[i]);
}
vector<Coor> Vertex;
int Size = Convex.size();
Vertex.resize(Size);
for(int i=Size-1; i>=0; i--) {
Vertex[i] = Convex.top();
Convex.pop();
}
int LPoint = 0, RPoint = 0;
for(int i=0; i<Size; i++) {
if(Vertex[i].x < Vertex[LPoint].x) LPoint = i;
if(Vertex[i].x > Vertex[RPoint].x) RPoint = i;
}
int DiaSq = DistSq(Vertex[LPoint], Vertex[RPoint]);
Coor Origin; Origin.x = 0, Origin.y = 0;
for(int i=0; i<Size; i++) {
if(CCW(Origin, Vertex[(LPoint+1)%Size]-Vertex[LPoint], Vertex[RPoint]-Vertex[(RPoint+1)%Size]) > 0)
LPoint = (LPoint + 1)%Size;
else RPoint = (RPoint + 1)%Size;
if(DistSq(Vertex[LPoint], Vertex[RPoint]) > DiaSq)
DiaSq = DistSq(Vertex[LPoint], Vertex[RPoint]);
}
printf("%d\n", DiaSq);
}
}
|
cs |
코드가 길어보이는데, 이는 Convex Hull 알고리즘과 코드가 같이 작성되어있기 때문입니다.
그리고 제가 이전에 다루지 않았던 개념이 있는데 C++에서는 연산자를 오버로딩해서 정의할 수 있습니다.
그래서 8행에서 13행의 코드를 보면 벡터 사이의 빼기 연산을 새로 정의해서, x좌표는 x좌표끼리, y좌표는 y좌표끼리 빼서 새로운 좌표를 만들도록 정의하였습니다.
회전하는 캘리퍼스 알고리즘은 77행부터 90행까지 소스코드가 총 15줄도 되지 않습니다.
코드를 보시면 우선 LPoint, RPoint는 기준이 되는 양 끝 점의 Index를 말합니다.
초기의 두 점은 x값이 가장 작은 점과 가장 큰 점 두 개로 잡습니다. (78행~80행)
DiaSq는 Diameter Square의 줄임말로 답이 되는 최대 거리의 제곱을 의미합니다.
어쨌든 초기 두 점의 거리를 우선 계산해서 DiaSq에 저장해줍니다.
그 다음 85행에서, 위의 두 벡터를 외적 계산해서 외적 값이 0보다 작으면 (위 그림에서 R 벡터가 더 아래쪽을 가리키므로 외적하면 음수가 됨, 오른손 법칙 써서 대충 방향 생각해보면 -z 방향이기 때문) R 벡터를 갱신해서, R 벡터쪽의 끝 점을 갱신해줍니다.
0보다 크면 L 벡터쪽의 끝 점을 갱신해서, 결론적으로는 모든 컨벡스 헐 다각형의 지름들을 계산해줄 수 있게 됩니다.
제출해보면 324ms가 소요되고 정답 처리를 받을 수 있습니다.
회전하는 캘리퍼스 알고리즘 구현이 사람들마다 다 다르게 되어 있어서 저는 제가 보기에 가장 편한 코드로 다시 풀어서 작성했습니다만 각자 보기 편한 코드를 참고하시는 것을 권장합니다.