볼록 껍질

어떤 문제를 푸는가

평면 위 점들이 주어졌을 때, 그 모든 점을 포함하는 가장 작은 볼록 다각형
(볼록 껍질, convex hull)을 구합니다. 점들을 고무줄로 감쌌을 때 만들어지는
바깥 윤곽이라고 생각하면 됩니다. 지름(가장 먼 두 점), 최소 외접 도형, 충돌
영역 등 기하 문제의 기반입니다.

볼록이란

다각형이 볼록 하다는 것은, 경계를 따라 한 바퀴 돌 때 항상 같은 방향
(예: 계속 좌회전) 으로만 꺾인다는 뜻입니다. 어딘가에서 반대로 꺾이면(우회전)
오목한 부분이 생긴 것입니다. CCW(외적 부호)로 이 회전 방향을 판정합니다.

그라함 스캔 / 모노톤 체인의 아이디어

대표 알고리즘은 두 가지지만 원리는 같습니다: 점을 정렬한 뒤, 스택에 쌓아
가며 볼록을 깨는 점을 제거 합니다.

모노톤 체인(Andrew's monotone chain):

1. 점들을 \(x\) 좌표(같으면 \(y\)) 기준으로 정렬한다.
2. 왼쪽→오른쪽으로 훑으며 아래 껍질(lower hull) 을 만든다. 새 점을 추가할
   때, 직전 두 점과 함께 보아 좌회전이 아니면(우회전/일직선) 직전 점을
   스택에서 빼낸다.
3. 오른쪽→왼쪽으로 다시 훑으며 같은 방식으로 위 껍질(upper hull) 을 만든다.
4. 둘을 이으면 전체 볼록 껍질.

왜 옳은가

볼록 껍질의 경계는 정렬 순서대로 보면 "한 방향으로만 꺾이는" 점들의 수열입니다.
스택에 점을 쌓다가 직전 세 점이 잘못된 방향(오목을 만드는 회전)을 이루면, 가운데
점은 껍질에 속할 수 없으므로 제거합니다. 이 과정을 거치면 스택에는 올바른 회전
방향을 유지하는 점들만 남아, 정확히 껍질의 한쪽 경계가 됩니다.

복잡도

정렬이 비용을 지배합니다. 각 점은 스택에 한 번 들어가고 최대 한 번 빠지므로
스캔 자체는 선형입니다.

경계 처리 — 일직선 위의 점

세 점이 일직선(CCW = 0)일 때 가운데 점을 껍질에 포함할지 말지 는 문제
정의에 따라 다릅니다. 보통은 제거(엄격한 볼록 껍질)하지만, "경계 위 점도
세라"는 문제면 포함합니다. 이 한 끗 차이가 정답을 가르므로 조건을 꼭 확인
하세요. 다음 강의에서 정수 안전 구현을 봅니다.

모노톤 체인 구현 (C++, 정수)

CCW는 외적으로 계산해 부동소수 오차를 없앱니다.

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

struct P { ll x, y; };
bool operator<(const P& a, const P& b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}
// 양수: 반시계(좌회전)
ll cross(const P& O, const P& A, const P& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<P> convexHull(vector<P> p) {
    int n = p.size(), k = 0;
    if (n <= 2) return p;
    sort(p.begin(), p.end());
    vector<P> h(2 * n);
    // 아래 껍질
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    // 위 껍질
    for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);           // 마지막은 시작점과 중복이므로 제거
    return h;
}

<= 0은 일직선 위 점을 제거 합니다(엄격한 볼록 껍질). 경계 위 점도
포함하려면 < 0으로 바꿉니다 — 문제 조건에 맞추는 핵심 한 줄입니다.

오버플로 주의

좌표가 최대 \(10^9\)이면 cross의 곱이 약 \(4 \times 10^{18}\)까지 커집니다.
반드시 long long (드물게 __int128)으로 받아야 합니다. 기하의 단골
함정입니다.

파이썬 구현

def convex_hull(pts):
    pts = sorted(set(pts))
    if len(pts) <= 2:
        return pts

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    lower = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]   # 끝점 중복 제거

흔한 함정

• 오버플로 — cross는 long long. 가장 자주 틀림.
• 일직선 처리 — <= 0 vs < 0을 문제 정의에 맞게. 경계 점 포함 여부.
• 중복/동일 점 — 같은 점이 여럿이면 set으로 제거하거나 비교에서 처리.
• 점이 2개 이하 — 별도 반환(다각형이 안 됨).
• 끝점 중복 — 아래·위 껍질을 이을 때 시작·끝점이 겹치므로 하나씩 잘라냄.

응용 패턴

• 다각형 넓이/둘레 — 껍질의 신발끈 공식·변 길이 합.
• 가장 먼 두 점(지름) — 껍질 위에서 회전하는 캘리퍼스로 \(O(N)\)(상위 단원).
• 점이 다각형 안인가 — 볼록 다각형이면 CCW 부호 일관성으로 \(O(\log N)\).
• 최소 외접 직사각형/원 — 껍질 위 점들만 고려.
• 컨벡스 헐 트릭 — 직선들의 하한 껍질로 DP 가속(상위 단원).

볼록 껍질은 "회전 방향이 한쪽으로만 유지된다"는 성질 위에서 정렬 + 스택으로
\(O(N \log N)\)에 구해집니다. CCW를 정수로 안전하게 다루는 습관이 모든 기하
응용의 안정성을 좌우합니다.

출제 신호

• "\(N\)개의 점을 모두 감싸는 최소 둘레/최소 울타리/볼록 다각형" — 직접 출제형
• "껍질 위의 점 개수", "가장 바깥의 점들만 남기기"
• 응용 신호: "가장 먼 두 점"(껍질 + 회전 캘리퍼스), "점 집합의 지름",
  "두 점 집합을 직선으로 분리할 수 있는가"
• 제약 신호: \(N \le 10^5{\sim}10^6\) + 좌표가 정수 — 정렬 \(O(N \log N)\) +
  스택 한 번이라는 모노톤 체인의 전형적 크기이고, 정수 좌표는 CCW를 정수로
  안전하게 계산하라는 뜻입니다.

최댓값을 찾는 많은 기하 문제("가장 먼", "가장 바깥")는 답이 껍질 위에만
존재한다는 성질 때문에, 먼저 껍질로 후보를 \(N\)개에서 껍질 크기로 줄이는
전처리로 쓰입니다.

풀이 결정 절차

1. 점을 (x, y) 사전순 정렬합니다 — 모노톤 체인의 전제입니다.
2. 아래 껍질, 위 껍질을 각각 스택으로 만들고 이어 붙입니다.
3. 일직선 위의 점 포함 여부를 문제에서 확인합니다 — "꼭짓점 개수"를
   묻는 문제는 공선점 제외(<= 0에서 pop), "껍질 위 모든 점"을 세는 문제는
   포함(< 0에서만 pop). 이 한 글자가 정답/오답을 가릅니다.
4. 답이 껍질 자체인지(둘레, 꼭짓점), 껍질 위의 후속 계산인지(캘리퍼스,
   넓이) 구분해 다음 단계를 계획합니다.

자주 하는 실수

• CCW 오버플로 — 좌표 \(10^9\)면 외적이 \(\approx 4 \times 10^{18}\)로
  long long 경계까지 갑니다. 외적은 무조건 long long, 그 곱을 다시
  곱하는 일이 없도록 부호만 쓰세요. 1순위 오답 원인입니다.

using ll = long long;
ll cross(const P& o, const P& a, const P& b) {
    return (a.x - o.x) * (ll)(b.y - o.y) - (a.y - o.y) * (ll)(b.x - o.x);
}

vector<P> hull(vector<P> p) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());   // 중복 점 제거
    if (p.size() <= 2) return p;                     // 퇴화: 점 1~2개
    vector<P> lo, up;
    for (auto& q : p) {                              // 아래 껍질
        while (lo.size() >= 2 && cross(lo[lo.size()-2], lo.back(), q) <= 0)
            lo.pop_back();                           // 공선 제외 규칙
        lo.push_back(q);
    }
    for (int i = (int)p.size() - 1; i >= 0; i--) {   // 위 껍질 (역방향)
        while (up.size() >= 2 && cross(up[up.size()-2], up.back(), p[i]) <= 0)
            up.pop_back();
        up.push_back(p[i]);
    }
    lo.pop_back(); up.pop_back();                    // 양 끝점 중복 제거
    lo.insert(lo.end(), up.begin(), up.end());
    return lo;
}

• 끝점 중복 제거 누락 — 아래·위 껍질을 이으면 시작점과 끝점이 두 번
  들어갑니다. 각 체인의 마지막 점을 빼고 이어 붙이세요. 꼭짓점 개수를
  묻는 문제에서 +2로 틀리는 원인입니다.
• 중복 점 / 모든 점이 한 직선 — 중복 점은 정렬 후 unique로 제거,
  점이 전부 공선이면 껍질이 다각형이 되지 않으므로(둘레 = 양 끝 거리의 2배
  같은 정의 문제) 문제의 정의를 다시 읽고 별도 처리합니다.
• 공선 규칙을 두 체인에서 다르게 적용 — 아래는 <= 0, 위는 < 0처럼
  섞이면 한쪽 변의 공선점만 들어가 개수가 어긋납니다. 두 체인은 같은 규칙으로.
• 둘레/넓이의 실수 처리 — 넓이는 신발끈 공식으로 정수(2배 넓이) 로
  유지하고 마지막에만 나누는 것이 안전합니다. 둘레만 sqrt로 실수 전환.

연습 방법

사이드바 연습 목록의 기본 껍질(꼭짓점 개수) 문제로 모노톤 체인을 보지 않고
쓸 수 있게 만든 뒤, 공선점 포함 변형, 둘레/넓이 계산, 가장 먼 두 점(회전
캘리퍼스) 순으로 확장하세요. 제출 전 점검 루틴 — long long 외적, 중복 점,
공선 등호, 끝점 중복, 점 2개 이하 — 다섯 가지를 체크리스트로 쓰면 기하
특유의 "한 끗 오답"이 크게 줄어듭니다. 태그된 문제 3문제 이상 해결 시
마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.