기하 알고리즘

정수로 안전한 CCW (C++)

좌표가 정수면 외적도 정수이므로 부동소수 오차가 원천적으로 0 입니다. 값 대신 부호만
돌려주는 습관을 들이면 이후 비교에서 다시 곱하다 넘치는 사고를 막습니다.

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

struct P { ll x, y; };

// +1: 반시계, -1: 시계, 0: 일직선
int ccw(const P& a, const P& b, const P& c) {
    ll v = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return (v > 0) - (v < 0);
}

오버플로 경계. 좌표가 최대 \(10^9\)이면 차 \((b.x-a.x)\)는 최대 \(2\times10^9\), 곱은
약 \(4\times10^{18}\)까지 커집니다. long long의 한계 \(\approx9.2\times10^{18}\) 안이라 아슬아슬하게
버티지만, 좌표가 \(10^9\)를 넘거나 중간에 좌표를 더하면 넘칩니다. 그때는 __int128을 씁니다.

int ccw128(const P& a, const P& b, const P& c) {
    __int128 v = (__int128)(b.x - a.x) * (c.y - a.y)
               - (__int128)(b.y - a.y) * (c.x - a.x);
    return (v > 0) - (v < 0);
}

선분 교차 — 공선까지 완전 처리 (C++)

// 공선일 때 c가 선분 [a,b] 위에 있는가 (바운딩 박스 검사)
bool onSeg(const P& a, const P& b, const P& c) {
    return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)
        && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool operator<=(const P& a, const P& b) {           // 사전순 (정규화용)
    return a.x != b.x ? a.x < b.x : a.y <= b.y;
}

bool intersect(P a, P b, P c, P d) {
    int ab = ccw(a, b, c) * ccw(a, b, d);
    int cd = ccw(c, d, a) * ccw(c, d, b);
    if (ab == 0 && cd == 0) {           // 네 점 공선 → 구간 겹침으로 판정
        if (b <= a) swap(a, b);
        if (d <= c) swap(c, d);
        return c <= b && a <= d;        // 정렬 후 겹침 조건
    }
    return ab <= 0 && cd <= 0;          // 끝점 닿음(=0)도 교차로 포함
}

• ab <= 0 && cd <= 0 — 끝점이 다른 선분에 닿는 경우까지 교차 로 봅니다(약한 교차).
  끝점 닿음을 교차로 치지 않으려면(강한/진짜 교차) 두 곱 모두 < 0으로 바꿉니다.
• 공선 케이스는 두 선분을 각각 사전순으로 정규화한 뒤 1차원 구간 \([a,b]\)와 \([c,d]\)의 겹침
  (\(c\le b\) 그리고 \(a\le d\), 여기서 비교는 사전순)으로 판정합니다.

검증 예시. 겹치는 공선: \(A(0,0)B(4,0)\), \(C(2,0)D(6,0)\) → 정규화 후 \(c(2,0)\le b(4,0)\) 그리고
\(a(0,0)\le d(6,0)\) 참 → 교차. 떨어진 공선: \(C(5,0)D(6,0)\) → \(c(5,0)\le b(4,0)\) 거짓 → 비교차.
한 점 접촉: \(C(4,0)D(6,0)\) → \(c(4,0)\le b(4,0)\) 참, \(a(0,0)\le d(6,0)\) 참 → 교차(끝점 닿음).

파이썬 구현

파이썬 정수는 자동 다정밀도라 오버플로 걱정이 없습니다.

def ccw(a, b, c):
    v = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
    return (v > 0) - (v < 0)

def on_seg(a, b, c):
    return min(a[0],b[0]) <= c[0] <= max(a[0],b[0]) and \
           min(a[1],b[1]) <= c[1] <= max(a[1],b[1])

def intersect(a, b, c, d):
    ab = ccw(a,b,c) * ccw(a,b,d)
    cd = ccw(c,d,a) * ccw(c,d,b)
    if ab == 0 and cd == 0:                 # 공선: 구간 겹침
        a, b = sorted((a, b)); c, d = sorted((c, d))
        return c <= b and a <= d
    return ab <= 0 and cd <= 0

흔한 함정

• 오버플로 — 가장 자주 틀립니다. 좌표가 크면 long long, 넘으면 __int128. 부호만 반환.
• 공선(=0) 누락 — 곱의 부호만 보면 \(0\)을 놓쳐 끝점 닿음·구간 겹침을 오판합니다.
• 부동소수 도피 — 기울기·교점 좌표를 실수로 구하면 수직선과 오차에 당합니다. 정수는 끝까지 정수로.
• 끝점 포함 여부 — "닿음이 교차인가"를 문제에서 확인하고 <=/<를 결정.
• 퇴화 선분(길이 0) — 같은 두 점으로 된 입력은 점-선분 포함으로 별도 처리.

출제 신호 — 언제 이 도구를 꺼내는가

• 입력이 좌표(점·선분·다각형)이고 방향(시계/반시계/일직선), 선분 교차, 점의 다각형 내부 여부를 묻는 문제.
• "두 길/울타리가 만나는가", "겹치는가" 같은 서사로 변장한 교차 판정.
• 좌표 범위가 \(|x|,|y|\le10^9\)처럼 큰 정수 — 실수 기하가 아니라 정수 CCW 로 풀라는 신호.
• 볼록 껍질·다각형 넓이·각도 정렬 등 상위 기하 알고리즘의 부품 으로 항상 등장.

응용 1 — 다각형 넓이 (신발끈 공식)

CCW의 크기가 삼각형 넓이의 2배라는 사실에서 곧바로 나옵니다. 원점을 기준으로 한 삼각형들의
부호 있는 넓이를 모두 더하면, 오목·볼록에 관계없이 단순 다각형의 넓이가 됩니다.

$$ \text{Area}=\frac12\left|\sum_{i=0}^{n-1}(x_i y_{i+1}-x_{i+1}y_i)\right| $$

ll area2(const vector<P>& p) {          // 넓이의 2배 (정수로 정확)
    ll s = 0; int n = p.size();
    for (int i = 0; i < n; i++) {
        const P& a = p[i]; const P& b = p[(i + 1) % n];
        s += a.x * b.y - b.x * a.y;      // = ccw(원점,a,b)
    }
    return llabs(s);                     // 실제 넓이는 s/2, 홀수면 .5
}

넓이의 2배 를 정수로 유지하면 반정수 넓이까지 오차 없이 다룰 수 있습니다.

응용 2 — 점의 다각형 내부 판정

볼록 다각형 이면 모든 변에 대해 CCW 부호가 일관되면 내부입니다(\(O(n)\); 정점 각도 이분탐색으로
\(O(\log n)\)까지 가능). 일반(오목) 다각형 이면 점에서 오른쪽으로 쏜 반직선이 변과 몇 번
교차하는지 세는 홀짝 규칙(ray casting) 을 씁니다 — 홀수면 내부.

// 일반 다각형: 광선 교차 홀짝. 경계 위 점은 별도 처리 필요.
bool inPolygon(const vector<P>& poly, P q) {
    int n = poly.size(), cnt = 0;
    for (int i = 0; i < n; i++) {
        P a = poly[i], b = poly[(i + 1) % n];
        bool cond = (a.y > q.y) != (b.y > q.y);      // y구간이 q를 감싸는가
        if (cond) {
            // 교점의 x가 q.x보다 오른쪽인가 (외적으로 나눗셈 없이)
            ll lhs = (b.x - a.x) * (q.y - a.y);
            ll rhs = (q.x - a.x) * (b.y - a.y);
            if (a.y < b.y ? lhs > rhs : lhs < rhs) cnt ^= 1;
        }
    }
    return cnt & 1;
}

응용 3 — 각도 정렬 (나눗셈 없는 극각 비교)

기준점을 중심으로 점들을 반시계 순으로 정렬할 때, \(\operatorname{atan2}\)의 부동소수 대신 CCW를
비교자로 씁니다. 먼저 위/아래 반평면 으로 나눈 뒤 같은 반평면 안에서 CCW로 좌우를 정합니다.

int half(const P& p) { return (p.y != 0) ? (p.y > 0 ? 1 : -1)
                                         : (p.x >= 0 ? 1 : -1); }
bool angleCmp(const P& a, const P& b) {          // 원점 기준 극각 오름차순
    int ha = half(a), hb = half(b);
    if (ha != hb) return ha < hb;
    ll cr = a.x * b.y - a.y * b.x;               // = ccw(원점,a,b)
    return cr > 0;                               // 같으면 정렬 무관(공선)
}

함정 총정리와 변형

• 오버플로가 1순위. 넓이 합·각도 비교에서도 곱이 커지므로 long long/__int128을 유지.
• 경계 위 점. 내부 판정에서 "경계도 내부로 보는가"를 문제에서 확인 — ray casting은 경계에서
  불안정하므로, 경계 포함이 중요하면 각 변에 대해 onSeg를 먼저 검사.
• 공선/퇴화. 넓이 0(모두 공선), 길이 0 선분, 자기 교차 다각형은 별도 가정 확인.
• 강/약 교차. 끝점 닿음 포함 여부에 따라 <=↔<. 문제 정의 한 줄이 정답을 가릅니다.
• 변형: 다각형-다각형 교차, 볼록 판정, 반직선/직선 교차 모두 위 CCW 부품의 조합으로 확장됩니다.

태그된 연습 문제를 CCW 단독 → 접촉 불포함 교차 → 접촉·공선 포함 교차 → 넓이/내부 판정 순으로
풀며, 반례(겹치는 구간·한 점 접촉·떨어진 공선)를 직접 만들어 자기 코드로 검증하는 습관이 가장
효과적입니다.

모노톤 체인 구현 (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;
}
bool operator==(const P& a, const P& b) { return 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) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());   // 중복 점 제거
    int n = p.size(), k = 0;
    if (n <= 2) return p;
    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;                 // 반시계 방향, 시작점 1회만 포함
}

오버플로. 좌표가 최대 \(10^9\)이면 cross의 곱이 약 \(4\times10^{18}\)까지 커집니다. 반드시
long long(넘으면 __int128)을 씁니다. 기하의 단골 함정입니다.

공선 처리 — <= 0 대 < 0

핵심 한 줄은 스택 pop 조건입니다.

• cross(...) <= 0 — 일직선(공선) 점을 제거. 껍질 변 위의 중간 점이 결과에서 빠집니다.
  (엄격한 볼록 껍질)
• cross(...) < 0 — 공선 점을 유지. "경계 위의 모든 점을 껍질에 포함"하라는 문제에 씁니다.

문제 조건("껍질 위 점의 개수를 세라" 등)에 따라 이 부등호 하나로 정답이 갈립니다. < 0으로 바꾸면
한 변에 여러 공선 점이 남으므로, 결과에서 중복·역방향 정리를 신경 써야 합니다.

파이썬 구현

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]        # 끝점 중복 제거

그라함 스캔 변형 (극각 정렬)

가장 아래-왼쪽 점을 피벗으로 잡고 나머지를 극각(반시계) 순으로 정렬한 뒤, 스택으로 우회전을
제거합니다. 결과는 같지만 정렬 비교자로 CCW를 써야 하고 동일 각도·공선 처리가 까다로워, 실전에서는
모노톤 체인을 더 선호합니다.

// 피벗(pivot) 기준 극각 비교: 나눗셈 없이 CCW로
P pivot;
bool polarCmp(const P& a, const P& b) {
    ll c = cross(pivot, a, b);
    if (c != 0) return c > 0;                        // 반시계 먼저
    // 같은 각도면 피벗에서 가까운 점 먼저 (공선 안정화)
    ll da = (a.x-pivot.x)*(a.x-pivot.x) + (a.y-pivot.y)*(a.y-pivot.y);
    ll db = (b.x-pivot.x)*(b.x-pivot.x) + (b.y-pivot.y)*(b.y-pivot.y);
    return da < db;
}

흔한 함정

• 오버플로 — cross는 long long/__int128. 가장 자주 틀립니다.
• 공선 부등호 — <= 0(제거) vs < 0(포함)을 문제 정의에 맞춰 선택.
• 중복·동일 점 — sort + unique(파이썬 set)로 먼저 정리.
• 점이 2개 이하 — 다각형이 안 되므로 별도 반환.
• 모든 점이 공선 — 껍질이 선분으로 퇴화. 상위 알고리즘이 이를 가정하지 않으면 예외 처리.
• 끝점 중복 — 아래·위 껍질을 이을 때 시작·끝점이 겹치므로 하나씩 잘라냅니다.

출제 신호

• 점 집합에서 "가장 바깥 윤곽", "감싸는 최소 볼록 다각형", "껍질 위 점의 개수".
• 껍질을 부품 으로 쓰는 문제: 가장 먼 두 점(지름), 최소 외접 사각형/원, 폭, 두 볼록 도형의 최소
  거리 — 모두 껍질을 먼저 구한 뒤 회전하는 캘리퍼스(상위 단원)로 잇습니다.
• 컨벡스 헐 트릭 처럼 "직선들의 하한 껍질"로 DP를 가속하는 최적화형.

응용 1 — 넓이·둘레와 지름

껍질을 구하면 신발끈 공식으로 넓이(2배를 정수로), 변 길이 합으로 둘레를 즉시 얻습니다. 가장 먼 두
점(지름)은 껍질 위에서만 나타나므로, 껍질 정점 수를 \(h\)라 하면 회전하는 캘리퍼스로 \(O(h)\)에
찾습니다(다음 단원). 무작정 \(O(N^2)\)로 모든 쌍을 보는 대신 껍질로 후보를 줄이는 것이 정석입니다.

ll area2(const vector<P>& h) {          // 껍질 넓이의 2배
    ll s = 0; int n = h.size();
    for (int i = 0; i < n; i++)
        s += h[i].x * h[(i+1)%n].y - h[(i+1)%n].x * h[i].y;
    return llabs(s);
}

응용 2 — 볼록 다각형 안의 점 판정 \(O(\log N)\)

껍질이 반시계로 정렬돼 있으면, 첫 정점을 기준으로 부채꼴을 이분탐색해 점이 어느 삼각형에
속하는지 찾고 CCW 한 번으로 내부를 확정합니다.

// h: 반시계 볼록 다각형. 내부(경계 포함)면 true.
bool inConvex(const vector<P>& h, P q) {
    int n = h.size();
    if (cross(h[0], h[1], q) < 0 || cross(h[0], h[n-1], q) > 0) return false;
    int lo = 1, hi = n - 1;
    while (hi - lo > 1) {                 // q가 속한 부채꼴 이분탐색
        int mid = (lo + hi) / 2;
        (cross(h[0], h[mid], q) >= 0 ? lo : hi) = mid;
    }
    return cross(h[lo], h[hi], q) >= 0;   // 마지막 변 안쪽인가
}

응용 3 — 컨벡스 헐 트릭(개념)

DP 전이 \(dp[i]=\min_j(a_j\cdot x_i+b_j)\) 형태는 직선 \(y=a_j\ x+b_j\)들의 하한 껍질(lower envelope)
위에서 최소를 찾는 문제로 바뀝니다. 기울기 순으로 직선을 추가하며 필요 없는 직선을 pop하는 구조가
바로 볼록 껍질의 1차원판입니다. 쿼리·기울기가 단조면 \(O(N)\), 아니면 Li Chao 트리로 \(O(N\log)\).
여기서도 교점 비교를 정수 외적 으로 처리하면 오차가 없습니다.

함정과 변형 총정리

• 오버플로가 여전히 1순위. 넓이·지름·헐 트릭 교점 모두 곱이 커지므로 long long/__int128.
• 공선 정책 일관성. 지름·최소 외접처럼 껍질을 부품으로 쓸 때는 보통 공선 점을 제거(엄격)하는
  편이 후속 캘리퍼스가 깔끔합니다. 반대로 "경계 점 개수"를 물으면 포함.
• 퇴화 입력. 점 1~2개, 모든 점 공선, 모든 점 동일 — 상위 알고리즘 호출 전에 걸러냅니다.
• 동적/온라인 볼록 껍질. 점이 삽입·삭제되며 껍질을 유지해야 하면 균형 BST 기반의 동적 껍질
  (\(O(\log N)\) 삽입)로 확장합니다 — 상위 주제.
• 3D 볼록 껍질. 평면을 넘어가면 증분법·선물 포장 등 별도 기법이 필요합니다(범위 밖).

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

지름 (가장 먼 두 점) — C++ 정수 구현

껍질 h는 앞 단원의 convexHull로 얻은 반시계·공선 제거 상태라고 가정합니다. 거리 제곱과
전진 판정 모두 정수 외적으로 처리합니다.

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

struct P { ll x, y; };
ll cross(P O, P A, P B) {                // (A-O) x (B-O)
    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;
}

// 볼록 껍질 h(반시계, 공선 제거) 위에서 지름^2 과 두 점의 인덱스
ll diameter2(const vector<P>& h, int& bi, int& bj) {
    int n = h.size();
    if (n == 1) { bi = bj = 0; return 0; }
    if (n == 2) { bi = 0; bj = 1; return dist2(h[0], h[1]); }
    ll best = 0; int j = 1;
    for (int i = 0; i < n; i++) {
        int ni = (i + 1) % n;
        // 밑변 h[i]->h[ni] 에 대해 가장 먼 정점까지 j를 전진
        while (cross(h[i], h[ni], h[(j+1)%n]) > cross(h[i], h[ni], h[j]))
            j = (j + 1) % n;
        // 밑변 양 끝과 대응점 사이 거리 후보 갱신
        for (int e : {i, ni}) {
            ll d = dist2(h[e], h[j]);
            if (d > best) { best = d; bi = e; bj = j; }
        }
    }
    return best;
}

• cross 비교로 전진 을 판정하므로 제곱근·나눗셈이 없습니다.
• 밑변의 양 끝점 \(h[i], h[ni]\)을 모두 후보로 넣는 것이 흔한 실수 방지 포인트입니다. 한쪽만
  보면 특정 안티포달 쌍을 놓칩니다.
• 실제 지름은 \(\sqrt{\text{best}}\)지만, 문제에서 제곱 비교 만 요구하면 정수 best를 그대로
  씁니다(오차 0).

예시. 껍질 \((0,0),(4,0),(4,3),(0,3)\)의 지름은 대각선 \((0,0)\)–\((4,3)\)으로 \(d^2=25\), 즉 \(5\)입니다.

두 볼록 다각형 사이 최소 거리

두 볼록 다각형 \(P,Q\) 사이 최소 거리는 각각 아래/위 지지선을 맞물려 캘리퍼스로 훑으며, 점-선분
거리 후보를 갱신해 \(O(|P|+|Q|)\)에 구합니다. 정수 좌표라면 거리 제곱과 사영 판정을 유리수(분자·분모
정수)로 다뤄 오차를 피할 수 있습니다.

// 점 p 와 선분 ab 사이 거리^2 (부동소수). 대량 비교엔 유리수화 권장.
double segDist2(P a, P b, P p) {
    ll dx = b.x-a.x, dy = b.y-a.y;
    ll ap_ab = (p.x-a.x)*dx + (p.y-a.y)*dy;
    ll ab2 = dx*dx + dy*dy;
    double t = ab2 ? (double)ap_ab / ab2 : 0.0;
    t = max(0.0, min(1.0, t));            // 선분 밖이면 끝점으로 클램프
    double cx = a.x + t*dx, cy = a.y + t*dy;
    double ex = p.x - cx, ey = p.y - cy;
    return ex*ex + ey*ey;
}

흔한 함정

• 껍질 전제 위반 — 입력이 볼록이 아니거나 공선 점이 남아 있으면 단조성이 깨져 오답. 반드시
  엄격 껍질 을 먼저 만듭니다.
• 밑변 한쪽만 후보 — 위 코드처럼 \(i\)와 \(ni\) 양 끝을 모두 비교해야 모든 안티포달 쌍을 봅니다.
• \(N\le2\) 퇴화 — 점 1~2개는 별도 분기. 모든 점 공선이면 껍질이 선분이 되므로 지름은 양 끝 거리.
• 제곱근 남용 — 거리 크기 비교엔 \(d^2\)(정수)만 쓰고, 실제 길이가 필요할 때만 마지막에 한 번
  \(\sqrt{}\). 중간 비교에 실수를 끼우지 마세요.
• 오버플로 — \(d^2\)는 좌표 \(10^9\)에서 \(\approx8\times10^{18}\)까지 갑니다. long long 경계선,
  넘으면 __int128.

응용 1 — 다각형의 폭(최소 지지선 간격)

폭은 다각형을 감싸는 평행선 사이의 최소 간격입니다. 반드시 어느 한 지지선이 껍질의 한 변과
겹치므로, 각 변을 밑변으로 잡고 그 변에서 가장 먼 정점까지의 수직 거리 를 캘리퍼스로 훑어
최소를 취합니다. 수직 거리 \(=\dfrac{|\text{cross}(\vec{e},\vec{ep})|}{|\vec e|}\)이므로, 비교는
\(\dfrac{\text{cross}^2}{|\vec e|^2}\)(정수 분자/분모)로 하여 제곱근을 마지막까지 미룹니다.

// 최소 폭^2 을 유리수 비교로. width2 = cross^2 / edgeLen^2 의 최소.
// 반환은 (분자, 분모) 형태로 두어 오차 없는 비교가 가능.
pair<ll,ll> minWidth2(const vector<P>& h) {
    int n = h.size(); int j = 1;
    ll bn = -1, bd = 1;                          // best = bn/bd
    for (int i = 0; i < n; i++) {
        int ni = (i + 1) % n;
        while (llabs(cross(h[i], h[ni], h[(j+1)%n]))
             > llabs(cross(h[i], h[ni], h[j]))) j = (j + 1) % n;
        ll c = cross(h[i], h[ni], h[j]);         // 밑변에서 j까지 (넓이 2배)
        ll el = dist2(h[i], h[ni]);              // 밑변 길이^2
        // 수직거리^2 = c^2 / el.  bn/bd 와 c*c / el 비교
        if (bn < 0 || (__int128)c*c*bd < (__int128)bn*el) { bn = c*c; bd = el; }
    }
    return {bn, bd};
}

폭은 최소 외접 평행사변형·충돌 판정(분리축) 등에 그대로 쓰입니다.

응용 2 — 최소 외접 직사각형

넓이가 최소인 감싸는 직사각형은 반드시 한 변이 껍질의 한 변과 평행 합니다(회전 정리). 각 변을
기준 방향으로 삼아, 그 방향으로 가장 먼 정점(높이), 좌·우로 가장 먼 정점(폭)을 세 개의 캘리퍼스
로 동시에 전진시키며 넓이를 갱신합니다. 전체 \(O(H)\).

• 높이 접점: 밑변에서 외적 넓이가 최대인 정점(위 폭 코드와 동일한 전진).
• 좌/우 접점: 밑변 방향 벡터와의 내적(dot) 이 각각 최소·최대인 정점.

내적·외적 모두 정수이므로 넓이 비교(\(=\) 폭×높이, 유리수)를 오차 없이 처리할 수 있습니다. 둘레
최소 사각형도 같은 골격에서 목적 함수만 바꿉니다.

ll dot(P O, P A, P B) {                          // (A-O)·(B-O)
    return (A.x-O.x)*(B.x-O.x) + (A.y-O.y)*(B.y-O.y);
}

응용 3 — 두 다각형의 최대 거리 / 최대 삼각형

• 두 볼록 다각형의 가장 먼 두 점 도 두 다각형에 각각 캘리퍼스를 물려 \(O(|P|+|Q|)\)에 구합니다.
• 껍질 위 세 점으로 만드는 최대 넓이 삼각형 은 두 정점을 캘리퍼스로 전진시키며 세 번째 정점의
  외적 넓이를 최대화합니다(주의: 순수 이중 캘리퍼스는 반례가 있어, 안전하게는 각 밑변마다 대응점을
  단조 전진시키는 신중한 구현 또는 \(O(H^2)\) 보강이 필요).

함정과 변형 총정리

• 볼록·반시계·공선 제거 전제 를 항상 먼저 보장. 이것이 캘리퍼스 오답의 최대 원인입니다.
• 제곱근·나눗셈은 마지막에. 전진 판정과 크기 비교는 외적·내적·유리수(분자/분모)로. 실제 길이가
  필요할 때만 한 번 \(\sqrt{}\).
• 오버플로. \(c^2\), \(c^2\cdot d\) 형태는 쉽게 \(10^{18}\)를 넘습니다. 비교식에 __int128을 쓰세요.
• 퇴화. 껍질이 점·선분으로 줄어드는 입력(\(N\le2\), 전부 공선)은 별도 분기.
• 변형. 폭·최소 외접 사각형·두 다각형 거리·분리축 충돌 판정은 모두 "단조 전진하는 접점"이라는
  같은 골격에서 목적 함수만 바꿔 얻습니다. 골격을 한 번 체화하면 넓은 문제군이 열립니다.

반평면 교집합 구현 (C++)

반평면은 부동소수 교점을 다루므로 보통 double로 구현합니다. 아래는 각도 정렬 + 덱 의 표준
형태로, 앞 강의의 규약(직선의 왼쪽이 반평면)을 그대로 씁니다.

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;

struct P { double x, y; };
P operator+(P a, P b){ return {a.x+b.x, a.y+b.y}; }
P operator-(P a, P b){ return {a.x-b.x, a.y-b.y}; }
P operator*(P a, double t){ return {a.x*t, a.y*t}; }
double cross(P a, P b){ return a.x*b.y - a.y*b.x; }

struct Line {
    P p, d;              // 점 p, 방향 d. 반평면 = 직선의 '왼쪽'
    double ang;
    Line(){}
    Line(P a, P b){ p = a; d = b - a; ang = atan2(d.y, d.x); }
};
// q 가 반평면 안(왼쪽)인가
bool onLeft(const Line& l, P q){ return cross(l.d, q - l.p) > EPS; }
// 두 직선의 교점 (평행이 아님을 가정)
P inter(const Line& a, const Line& b){
    double t = cross(b.d, a.p - b.p) / cross(a.d, b.d);
    return a.p + a.d * t;
}
// 방향각 정렬. 각이 같으면 더 '안쪽(왼쪽)'인 직선을 앞에 둔다.
bool cmp(const Line& a, const Line& b){
    if (fabs(a.ang - b.ang) > EPS) return a.ang < b.ang;
    return cross(b.d, a.p - b.p) > 0;      // a 가 더 제약적이면 먼저
}

// 교집합 다각형의 꼭짓점(반시계). 비었으면 빈 벡터.
vector<P> halfPlaneIntersection(vector<Line> ls){
    sort(ls.begin(), ls.end(), cmp);
    int n = ls.size();
    deque<Line> dq;                        // 유효 직선
    deque<P> pt;                           // 인접 직선의 교점 (dq보다 하나 적음)
    for (int i = 0; i < n; i++){
        if (i && fabs(ls[i].ang - ls[i-1].ang) < EPS) continue;   // 같은 각 → 앞의 것만
        while (!pt.empty() && !onLeft(ls[i], pt.back()))  { pt.pop_back();  dq.pop_back();  }
        while (!pt.empty() && !onLeft(ls[i], pt.front())) { pt.pop_front(); dq.pop_front(); }
        if (!dq.empty()) pt.push_back(inter(dq.back(), ls[i]));
        dq.push_back(ls[i]);
    }
    // 앞뒤 맞물림: 뒤쪽 직선들이 맨 앞 직선 밖의 교점을 만들면 제거
    while (!pt.empty() && !onLeft(dq.front(), pt.back())){ pt.pop_back(); dq.pop_back(); }
    if (dq.size() < 3) return {};          // 공집합 또는 무계
    pt.push_back(inter(dq.back(), dq.front()));
    return vector<P>(pt.begin(), pt.end());
}

• onLeft가 엄격 부등호(> EPS) 인 점에 주의: 경계에 딱 닿는 퇴화를 안정적으로 다루려면 EPS로
  완충합니다. dq.size() < 3은 결과가 다각형을 이루지 못한 경우(공집합/무계)를 걸러냅니다.
• 같은 방향각 직선은 더 안쪽(제약적)인 것만 남기고 나머지는 건너뜁니다(cmp의 2차 기준 +
  루프의 continue).

검증. \(x\ge0\): Line({0,0},{0,1})(위로, 왼쪽=\(x\le0\)? 규약에 맞춰 방향을 잡아야 함),
실제로는 각 부등식을 "왼쪽" 규약에 맞도록 두 점 순서를 정합니다. 정사각형 4변을 반시계 경계로 주면
결과가 그 사각형으로 나오는지로 손검증하는 것이 가장 확실합니다.

무계 방지 — 경계 상자 추가

무계 영역을 유계로 만들려면 아주 큰 상자의 네 변을 반평면으로 미리 넣습니다.

double B = 1e9;                             // 좌표 범위보다 충분히 크게
vector<Line> box = {
    Line({-B,-B},{ B,-B}),                  // 아래
    Line({ B,-B},{ B, B}),                  // 오른쪽
    Line({ B, B},{-B, B}),                  // 위
    Line({-B, B},{-B,-B}),                  // 왼쪽 (반시계, 안쪽이 왼쪽)
};

이러면 답이 항상 유계 다각형이 되어 넓이·꼭짓점 처리가 단순해집니다. 다만 상자 크기 \(B\)를 너무
크게 잡으면 교점 좌표가 커져 정밀도가 나빠지니, 좌표 범위에 맞춰 적당히 잡습니다.

흔한 함정

• 평행선 나눗셈 — inter의 분모 cross(a.d,b.d)가 0(평행)이면 나눗셈 폭발. 같은 각 처리와
  덱 규칙이 이 상황을 애초에 만들지 않도록 막지만, 방향/부호 규약이 어긋나면 발생합니다.
• 각도 규약 불일치 — 모든 부등식을 "직선의 왼쪽" 하나로 통일하지 않으면 오답. 두 점 순서로
  방향을 맞추세요.
• EPS 선택 — 너무 크면 얇은 정답 영역을 없애고, 너무 작으면 경계 퇴화에서 흔들립니다. 좌표
  스케일에 맞춰 \(10^{-9}\sim10^{-6}\).
• 공집합/무계 미구분 — dq.size() < 3과 상자 기법으로 명시적으로 처리.

출제 신호

• 여러 선형 부등식/직선 이 주어지고 "동시에 만족하는 영역의 넓이/존재 여부"를 묻는 문제.
• 다각형의 핵(kernel) — 다각형 내부에서 모든 점을 볼 수 있는 관측 위치들의 집합.
• 2D 선형 계획법 — 목적 함수 최댓값이 실현 가능 영역(HPI 결과)의 꼭짓점에서 나옴.
• 여러 볼록 다각형의 교집합(각 다각형을 변마다 반평면으로 분해).

응용 1 — 다각형의 핵 (kernel)

단순 다각형이 반시계로 주어질 때, 각 변을 "내부가 왼쪽"인 반평면으로 바꿔 모두 교집합하면 그 결과가
바로 핵입니다. 핵이 비지 않으면 그 다각형은 별 모양(star-shaped) 이며, 핵 안의 아무 점에서나
다각형 전체를 볼 수 있습니다.

// 반시계 단순 다각형 poly 의 핵을 HPI로 구성
vector<Line> kernelHalfPlanes(const vector<P>& poly){
    vector<Line> ls; int n = poly.size();
    for (int i = 0; i < n; i++)
        ls.push_back(Line(poly[i], poly[(i+1)%n]));   // 내부가 왼쪽
    return ls;                                        // halfPlaneIntersection(ls)
}

결과 다각형이 비어 있으면(\(\text{dq.size}<3\)) 핵이 없는 것이고, 넓이 \(>0\)이면 별 모양입니다.
"경비원 한 명으로 전시장 전체를 볼 수 있는가" 류의 문제가 정확히 이 형태입니다.

응용 2 — 2D 선형 계획법

목적 \(\max (c_x x + c_y y)\)를 제약 \(A_i x + B_i y \le C_i\) 아래에서 푸는 문제는, 각 제약을 반평면으로
바꿔 실현 가능 영역을 HPI로 구한 뒤 꼭짓점만 후보로 목적 함수를 평가하면 됩니다(볼록 다각형의
선형 함수 최댓값은 꼭짓점에서). 실현 가능 영역이 비면 해가 없고, 무계면 목적 함수 방향에 따라
\(+\infty\)일 수 있습니다.

참고: 무작위 증분법(randomized incremental LP)은 2D LP를 기대 \(O(N)\)에 직접 풀지만, 영역 자체가
필요하면 HPI가 자연스럽습니다.

응용 3 — "최소 반지름으로 모두 감싸기" 류 매개변수 탐색

"반지름 \(r\)의 조건을 만족하는 배치가 존재하는가?"처럼 \(r\)을 이분탐색 하고, 각 후보 \(r\)에 대해
제약들이 반평면 집합으로 표현되면 HPI가 비지 않는지로 판정 함수를 만드는 패턴이 자주 등장합니다.
이때 \(r\)이 반평면의 오프셋 을 밀어(직선을 평행 이동) 실현 가능 영역이 언제 사라지는지를 봅니다.

함정과 변형 총정리

• 부동소수 본질. HPI는 교점이 유리수/무리수라 정수화가 어렵습니다. EPS 관리와 좌표 스케일링이
  정확성의 핵심입니다.
• 퇴화 처리. 세 반평면 이상이 한 점에서 만나는 경우, 완전히 평행한 반평면들, 폭 0의 정답 영역
  등은 EPS와 dq.size()<3 규칙으로 걸러냅니다.
• 각도 경계. \(\operatorname{atan2}\)가 \(\pm\pi\) 근처에서 감싸므로, 같은 방향각 판정과 정렬
  안정성에 주의합니다.
• 무계 vs 공집합 구분. 답을 "유계/공집합/무계" 셋으로 명확히 분류하고, 실무에선 경계 상자로
  무계를 유계화한 뒤 넓이를 재는 것이 안전합니다.
• 변형. 볼록 다각형 교집합, 핵, 2D LP, 매개변수 이분탐색의 판정 함수 — 모두 "부등식을 왼쪽
  반평면으로 통일 → 각도 정렬 → 덱" 이라는 하나의 골격에서 나옵니다.

inCircle 술어 — 정수로 정확하게 (C++)

델로네의 심장은 외접원 판정입니다. 좌표가 정수면 __int128로 오차 없이 계산합니다.

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

struct P { ll x, y; };
ll cross(P a, P b, P c){ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }

// a,b,c 가 반시계일 때: d 가 외접원 안이면 >0, 원 위면 0, 밖이면 <0
lll inCircle(P a, P b, P c, P d){
    lll ax=a.x-d.x, ay=a.y-d.y, bx=b.x-d.x, by=b.y-d.y, cx=c.x-d.x, cy=c.y-d.y;
    lll a2=ax*ax+ay*ay, b2=bx*bx+by*by, c2=cx*cx+cy*cy;
    return ax*(by*c2 - b2*cy)
         - ay*(bx*c2 - b2*cx)
         + a2*(bx*cy - by*cx);
}

오버플로 경계. 각 항은 좌표 차의 4차식입니다. 좌표가 \(|x|\le10^5\)이면 차는 \(2\times10^5\),
제곱은 \(4\times10^{10}\), 곱은 \(\approx10^{16}\)이라 long long도 위태롭습니다. 좌표가 크면
__int128(위 코드) 또는 좌표를 먼저 평행이동해 절댓값을 줄입니다. 위 코드처럼 \(d\)를 원점으로
당겨 빼면 값이 작아져 안전 여유가 커집니다.

증분 델로네 — flip으로 empty-circle 회복

증분법의 골격은 단순합니다.

1. 모든 점을 감싸는 아주 큰 가상의 큰 삼각형(super-triangle) 으로 시작한다.
2. 점을 하나씩 삽입한다. 그 점을 포함하는 삼각형을 찾아 세 개로 쪼갠다.
3. 새로 생긴 간선들에 대해 델로네 조건 위반(inCircle > 0) 이면 대각선을 뒤집는다(flip).
   뒤집기는 이웃으로 전파되며, 더 이상 위반이 없을 때까지 반복한다.
4. 모든 점을 넣은 뒤, 가상 삼각형의 꼭짓점과 이어진 삼각형들을 제거하면 델로네 완성.

// flip 판정의 핵심: 인접한 두 삼각형 (a,b,c) 와 (a,c,d) 가 사각형 a-b-c-d 를 이룰 때
// d 가 삼각형 (a,b,c) 의 외접원 안이면 대각선 (a,c) 를 (b,d) 로 뒤집어야 델로네가 된다.
bool shouldFlip(P a, P b, P c, P d){
    if (cross(a, b, c) <= 0) return false;     // (a,b,c) 가 반시계가 아니면 방향 보정 필요
    return inCircle(a, b, c, d) > 0;           // d 가 외접원 안 → flip
}

간선·삼각형을 인접 관계와 함께 관리하려면 보통 반쪽 간선(half-edge) 또는 삼각형 인접 배열로
자료구조를 둡니다. 각 삽입이 평균 상수 개의 flip만 유발하도록 점을 무작위 순서로 넣으면 기대
\(O(N\log N)\)입니다.

파이썬 — inCircle 판정 (오차 없는 정수)

def in_circle(a, b, c, d):
    ax, ay = a[0]-d[0], a[1]-d[1]
    bx, by = b[0]-d[0], b[1]-d[1]
    cx, cy = c[0]-d[0], c[1]-d[1]
    a2, b2, c2 = ax*ax+ay*ay, bx*bx+by*by, cx*cx+cy*cy
    return (ax*(by*c2 - b2*cy)
          - ay*(bx*c2 - b2*cx)
          + a2*(bx*cy - by*cx))   # >0: 안, 0: 원 위, <0: 밖 (a,b,c 반시계 가정)

파이썬 정수는 다정밀도라 오버플로가 없어, 델로네/보로노이의 참조 구현·검증기 로 이상적입니다.

흔한 함정

• 오버플로가 최대 함정 — inCircle은 좌표의 4차식. __int128 또는 좌표 평행이동으로 대비.
• 방향 가정 — inCircle은 \(a,b,c\)가 반시계 임을 전제. 시계면 부호가 뒤집히니 먼저 cross로
  방향을 확인/정렬.
• 공원(cocircular) 4점 이상 — inCircle \(=0\)인 퇴화. 델로네가 유일하지 않게 되므로 일관된
  타이브레이크(예: 좌표 사전순)로 결정론적으로 처리.
• 공선 사이트 — 세 점이 일직선이면 삼각형이 없어 외접원이 정의 안 됨. 별도 처리.
• 가상 삼각형 크기 — super-triangle을 충분히 크게 잡되, 정수 좌표를 유지하려면 안전한 큰 상수로.

출제 신호

• "각 지점에서 가장 가까운 사이트/시설", "최근접점 질의를 여러 번".
• "가장 큰 빈 원(사이트가 하나도 없는 최대 반지름 원)을 도심 안에 놓아라".
• "점들의 유클리드 최소 신장 트리", "최근접 쌍", "각 점의 최근접 이웃".
• 이들은 대개 델로네 간선 \(O(N)\)개 만 있으면 풀리므로, 보로노이를 직접 그리기보다 델로네를
  만들어 그래프로 넘기는 편이 실전적입니다.

응용 1 — 유클리드 최소 신장 트리 (EMST)

평면 점들의 EMST는 모든 완전그래프 간선이 아니라 델로네 간선만 봐도 충분하다는 정리가 있습니다
(EMST \(\subseteq\) Delaunay). 그래서:

1. 델로네 삼각분할을 만든다 → \(O(N)\)개의 후보 간선.
2. 각 간선에 유클리드 거리(제곱)를 얹어 일반 MST(크루스칼/프림)를 돌린다.

전체 \(O(N\log N)\). \(N^2\)개 간선을 다 보는 순진한 방법을 델로네가 \(O(N)\)개로 줄여 줍니다.

// 델로네 간선 목록 edges(사이트 인덱스 쌍)로 EMST 무게 합
ll dist2(P a, P b){ ll dx=a.x-b.x, dy=a.y-b.y; return dx*dx+dy*dy; }
// (u,v,dist2) 로 정렬 후 유니온-파인드 크루스칼 → 표준

거리 비교는 제곱(정수)으로 하고, 실제 길이 합이 필요하면 마지막에 \(\sqrt{}\)를 더합니다.

응용 2 — 최대 공터 원 (largest empty circle)

사이트가 하나도 들어오지 않는 가장 큰 원의 중심은 다음 후보 중 하나입니다.

• 보로노이 꼭짓점(세 사이트 등거리 = 델로네 삼각형의 외심), 또는
• 보로노이 변과 도심 경계(볼록 껍질/제약 영역)의 교점.

각 후보에서 가장 가까운 사이트까지의 거리를 재 최댓값을 취합니다. 델로네 외심들만 훑으면 후보가
\(O(N)\)개라 빠릅니다.

응용 3 — 최근접점/최근접 쌍

보로노이 셀은 곧 "이 사이트가 최근접인 영역"이므로, 질의점이 어느 셀에 있는지 점 위치 질의(point
location) 로 찾으면 최근접 사이트를 \(O(\log N)\)에 답할 수 있습니다. 최근접 쌍(가장 가까운 두
점)도 델로네 간선 중 최소 길이 간선으로 얻습니다 — 최근접 쌍은 항상 델로네 간선이기 때문입니다.

함정과 변형 총정리

• 정밀도 vs 정수. 델로네의 판정(cross, inCircle)은 정수로 정확히 가능하지만, 보로노이 꼭짓점
  좌표(외심)는 유리수/무리수라 실수로 다뤄야 합니다. 비교는 최대한 정수 술어로, 좌표 산출만 실수로.
• 퇴화. 공선 사이트(삼각분할 불가), 공원 4점(델로네 비유일), 중복 사이트는 사전에 정리하거나
  일관된 타이브레이크로.
• 경계·무계 셀. 바깥쪽 사이트의 보로노이 셀은 무한히 뻗습니다. 응용에서 도심(볼록 껍질/상자)으로
  잘라 유계화합니다.
• 직접 구현 부담. 완전한 증분 델로네는 자료구조(반쪽 간선)가 무겁습니다. 대회에서는 필요한
  간선(EMST·최근접)만 뽑는 목적형 구현이나, 검증엔 파이썬 정수 참조 구현을 병행하는 전략이 안전합니다.
• 변형. 가중 보로노이(파워 다이어그램), 최근접 대신 최원점(farthest-point) 보로노이(최소
  외접원에 사용) 등으로 확장됩니다.