여러 점들이 막 주어져 있을때 모든 점을 포함하는 볼록한 다각형을 의미한다. 볼록 껍질에에서 연속한 세 점을 한 쪽 방향으로 잡으면 모든 결과가 같다는 것을 이용하여, CCW 방식으로 구할 수 있다.
볼록껍질을 구하는 대표적인 알고리즘인 Graham Algorithm은 점들을 정렬하는데에서 시작한다.
- 볼록껍질에 무조건 들어가는 점 하나를 잡는다. (보통 가장 x좌표가, y좌표가 작은 점)
- 그 점을 기준으로 기울기 순으로 정렬한다. 같은 기울기면 거리 순으로 정렬.
- 점들을 그룹에 순서대로 넣는다.
- 넣으면서 그룹의 제일 최근 3점의 ccw가 옳지 않으면 그 세 점 중 중간 점을 뺀다.
- 3~4를 반복하면서 1번점까지 돌아온다.
코드로 구현하면 아래처럼 된다.
vector<point> convex_hull(vector<point>& points) {
int n = points.size();
if(n <= 3) return points;
for (int i=1;i<n;i++) {
if (points[i].y < points[0].y || (points[i].y == points[0].y && points[i].x < points[0].x)) {
swap(points[i], points[0]);
}
}
sort(points.begin()+1, points.end(), [&](point &a, point &b) { return cmp(a, b, points[0]); });
vector<point> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
for(int i=2;i<n;i++) {
while(hull.size()>=2&& ccw(hull[hull.size()-2], hull.back(), points[i]) <= 0)
hull.pop_back();
hull.push_back(points[i]);
}
return hull;
}캘리퍼스는 길이를 재는 도구이다. 회전하는 캘리퍼스는 놓여있는 점들 중 가장 먼 두 점의 거리를 구할때 돌면서 구하겠다는 뜻이다. two pointer 기반으로 이루어진다.
일단 점들중 가장 거리가 먼 두 점이 있다면 그 두 점은 모두 볼록 껍질 위에 있다라는 사실을 전제로 한다. 완벽히 증명은 되지 않아도 어느정도 직관적으로 이해할 수 있는 사실이다. 따라서 전체 점에서 볼록껍질을 잡고 시작한다. 볼록껍질에서 가장 먼 두 점 사이의 거리를 구하는 과정은 다음과 같이 이루어진다.
- 다각형의 한 점을 l, 다른 점을 r이라고 하자.
- l의 다음 점을 nl, r의 다음 점을 nr라고 하자.
- l과 r의 거리를 잰다.
- 벡터 l-nl와 벡터 r-nr의 CCW를 이용해 두 벡터가 정반대에 가까워지도록 l나 r을 한칸 돌린다.
- l이 처음으로 올때까지 반복한다.
회전하는 캘리퍼스 알고리즘으로 다각형에서 가장 먼 두 점의 거리를 구하는 문제로는 #9240, #10254, #1310, #8927 등이 있다.
위에서 설명한 방식을 그대로 구현하면 된다.
ld rotatingCalipers(vector<point>& p) {
ll n = p.size();
int l=0, r=1;
double res = hypot(p[l]-p[r]);
for (int t=0;t<n*2;t++){
int nl=(l+1)%n, nr=(r+1)%n;
double tmp = ccw(p[nl]-p[l], p[r]-p[nr]);
if (tmp>0) l=nl;
else if (tmp<0) r=nr;
else if (tmp==0) { l=nl; r=nr; }
res=min(res, hypot(p[l]-p[r]));
}
return res;
}회전하는 캘리퍼스 알고리즘으로 다각형에서 특정 점에서 가장 먼 변의 거리를 구하는 문제로는 #15028, #15420 등이 있다. 다각형을 어떤 구멍에 넣을 때 필요한 최소 폭을 구하는 문제가 많다.
점에서 가장 먼 변을 구할 때는 ccw가 0보다 큰 경우 l을 움직이고, 그렇지 않은 경우 r을 움직이면서 선분(l, nl) 또는 (r, nl)과 반대 점의 거리 최솟값을 구하면 된다.
ld rotating_calipers(vector<point>& hull) {
ll n=hull.size();
if (n<=2) return 0;
ll l=0, r=0;
for (int i=0;i<n;i++) {
if (p[i].x<p[l].x) l=i;
if (p[i].x>p[r].x) r=i;
}
ld res = numeric_limits<ld>::max();
point o = {0, 0};
for (int i=0;i<n;i++) {
ll nl = (l+1)%n, nr=(r+1)%n;
if (ccw(o, p[nl]-p[l], p[r]-p[nr]) > 0) {
res = min(res, dist(p[l], p[nl], p[r]));
l = nl;
} else {
res = min(res, dist(p[r], p[nr], p[l]));
r = nr;
}
}
return res;
}회전하는 캘리퍼스를 응용해 볼록다각형을 포함하는 가장 작은 직사각형을 구하는 문제를 해결할 수 있다. 이 방식을 사용하는 대표적인 문제로는 #19586, #9276, #10466가 있다.
볼록다각형을 포함하는 가장 작은 직사각형은 항상 해당 다각형의 한 변을 포함하는 원리를 활용한다. 우선 Convex Hull을 구한 뒤, Convex Hull의 각 변에 대한 반대쪽 점(u), 왼쪽(l), 오른쪽(r) 점을 각각 구해서 너비를 구하면 된다.
반대쪽 점은 점에서 가장 먼 변을 구하는 것과 동일한 방식으로 구하고, 왼쪽, 오른쪽 점은 기준 변과 r에서 다음 점으로의 변의 방향을 추가로 비교하여 구한다.
ld rotatingCalipers(vector<point>& p) {
if (n==1) { return 0; }
if (n==2) return 2*sqrt(dist(p[0], p[1]));
auto chk = [&cx, &n](int i, int j){
return (p[(i+1)%n]-p[i])/(p[(j+1)%n]-p[j])>0;
};
int u=1, l=1, r=1;
ld res = numeric_limits<ld>::max();
for (int i=0;i<n;i++){
if (u==i) u=(u+1)%n; while (chk(i,u)) u=(u+1)%n;
if (l==i) l=(l+1)%n; while (chk(i,l)||(p[(i+1)%n]-p[i])*(p[(l+1)%n]-p[l])<0) l=(l+1)%n;
if (r==i) r=(r+1)%n; while (chk(i,r)&&(p[(i+1)%n]-p[i])*(p[(r+1)%n]-p[r])>0) r=(r+1)%n;
point v1 = p[(i+1)%n]-p[i], v2 = {v1.y,-v1.x};
res = min(res, 2*((ld) dist(p[i], p[u], v1) + (ld) dist(p[l], p[r], v2)));
}
return res;
}참고