회전하는 캘리퍼스

무엇을 구하나

평면 위 점 집합에서 가장 먼 두 점 사이 거리(지름, diameter) 를 구하는 것이
대표 문제다. 모든 쌍을 보면 \(O(N^2)\)인데, 회전하는 캘리퍼스(rotating
calipers) 는 이를 \(O(N)\)(볼록 껍질 계산 포함 \(O(N \log N)\))에 푼다.

핵심 관찰

가장 먼 두 점은 반드시 볼록 껍질의 정점이다. 내부 점이나 변 위의 점은
껍질의 꼭짓점보다 멀 수 없기 때문이다. 그래서 먼저 볼록 껍질을 구하고,
그 위에서만 찾으면 된다.

대척점(antipodal pair)

볼록 다각형의 한 변에 평행한 두 지지선(caliper) 으로 다각형을 양쪽에서
집는다고 상상하자. 한 변을 기준으로 가장 먼 정점은, 그 변에서 가장 멀리
떨어진(수직 거리 최대) 정점이다. 변을 다각형 둘레를 따라 한 칸씩 돌리면,
"가장 먼 정점"도 같은 방향으로 단조롭게 한 칸씩 따라 돈다.

핵심 단조성: 기준 변을 반시계로 돌리면 그에 대응하는 최원점도 반시계로만
움직인다. 절대 뒤로 가지 않는다.

이 단조성 덕분에 두 포인터가 둘레를 각각 한 바퀴씩만 돌면 모든 대척점 쌍
(서로 평행한 지지선으로 동시에 집히는 정점 쌍)을 \(O(N)\)에 훑는다. 지름은 이
대척점 쌍들 중 거리 최대다.

거리 비교는 외적으로

"어느 정점이 변에서 더 먼가"는 외적(삼각형 넓이의 두 배) 으로 판정한다.
변 \(\overrightarrow{p_i p_{i+1}}\)에 대해 정점 \(q\)의 수직 거리에 비례하는 양은
\(\text{cross}(p_{i+1} - p_i,\ q - p_i)\)이다. 이 외적이 더 커지는 동안 포인터를
전진시키면 최원점을 찾는다. 부동소수 없이 정수 외적으로 비교하므로 오차가
없다.

다른 문제로의 확장

회전하는 캘리퍼스는 지름 외에도 여러 최적화를 같은 단조 진행으로 푼다.

• 최소 너비(width): 다각형을 감싸는 평행선 쌍의 최소 간격.
• 최소 넓이 외접 직사각형: 한 변이 껍질의 한 변과 평행해야 함이 보장됨.
• 두 볼록 다각형 사이 최소/최대 거리.

공통점은 "껍질의 한 요소(변/정점)를 돌리면, 대응하는 최적 요소가 단조롭게
따라 돈다"는 단조성이다. 이 성질만 확인되면 두 포인터로 선형에 끝난다.

지름(가장 먼 두 점) 구현

먼저 볼록 껍질을 구하고, 그 위에서 회전하는 캘리퍼스로 대척점 쌍을 훑는다.
거리는 제곱 거리로 비교해 정수 연산을 유지한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct P { ll x, y; };
ll cross(P O, P A, P B) {        // 외적 (OA x OB)
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
ll dist2(P a, P b) {
    ll dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}
// 볼록 껍질(반시계, 모노톤 체인) — convex_hull(pts) 별도 구현 가정
vector<P> convex_hull(vector<P> pts);

ll rotating_calipers(vector<P>& hull) {
    int n = hull.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(hull[0], hull[1]);
    ll best = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        // 변 (i, i+1)에서 가장 먼 정점 j를 단조 전진으로 찾는다
        int ni = (i + 1) % n;
        while (abs(cross(hull[i], hull[ni], hull[(j + 1) % n]))
             > abs(cross(hull[i], hull[ni], hull[j])))
            j = (j + 1) % n;
        best = max(best, dist2(hull[i], hull[j]));
        best = max(best, dist2(hull[ni], hull[j]));  // 양 끝 모두 비교
    }
    return best;
}

int main() {
    int n; scanf("%d", &n);
    vector<P> pts(n);
    for (auto& p : pts) scanf("%lld %lld", &p.x, &p.y);
    vector<P> hull = convex_hull(pts);
    ll d2 = rotating_calipers(hull);
    printf("%lld\n", d2);   // 제곱 거리 (필요하면 sqrt)
    return 0;
}

흔한 실수

• 포인터를 매번 0으로 리셋 — \(j\)는 바깥 루프 사이에 계속 이어서 전진해야
  단조성이 성립해 \(O(N)\)이 된다. 매번 처음부터 찾으면 \(O(N^2)\)다.
• 부동소수 거리 비교 — 거리를 sqrt로 비교하면 오차가 생긴다. 제곱
  거리(정수) 로 비교하라.
• 볼록 껍질 전처리 — 일직선 점, 중복 점, 시계/반시계 방향을 껍질 단계에서
  일관되게 처리해야 한다. 껍질 정점이 2개 이하인 경우도 따로 처리한다.
• 양 끝 비교 누락 — 변의 두 끝점 모두에 대해 최원점과의 거리를 갱신해야
  지름을 놓치지 않는다.

활용

회전하는 캘리퍼스는 볼록 껍질이 주는 단조 구조를 두 포인터로 활용하는
계산기하의 대표 기법이다. 핵심은 항상 "무엇이 무엇을 단조롭게 따라 도는가"를
먼저 규명하고, 그 비교를 정수 외적으로 정확히 구현하는 것이다.