CCW와 선분 교차

어떤 문제를 푸는가

세 점이 주어졌을 때 반시계/시계/일직선 중 어느 방향으로 도는지, 그리고 두
선분이 교차하는지 를 판정합니다. 컴퓨터 기하의 가장 기본 도구로, 볼록
껍질·다각형 포함 판정·선분 교차 등 거의 모든 기하 알고리즘의 토대입니다.

CCW — 외적(cross product)

점 \(A, B, C\)에 대해 벡터 \(\vec{AB}\)와 \(\vec{AC}\)의 외적의 부호를 봅니다.

$$ \text{ccw}(A, B, C) = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x) $$

이 값의 절댓값은 삼각형 \(ABC\) 넓이의 2배이기도 합니다. 즉 부호는 방향,
크기는 넓이를 동시에 담고 있습니다.

왜 부호가 방향을 주는가

외적은 두 벡터가 이루는 평행사변형의 부호 있는 넓이 입니다. \(\vec{AC}\)가
\(\vec{AB}\)의 왼쪽 에 있으면 양수, 오른쪽 이면 음수입니다. 회전
방향이 곧 "왼쪽/오른쪽에 있는가"이므로, 외적 부호 하나로 방향이 결정됩니다.

선분 교차 판정의 원리

선분 \(\overline{AB}\)와 \(\overline{CD}\)가 교차하려면:

• \(A, B\) 입장에서 \(C\)와 \(D\)가 서로 반대편 에 있어야 한다:
  \(\text{ccw}(A, B, C)\)와 \(\text{ccw}(A, B, D)\)의 부호가 다르다.
• 동시에 \(C, D\) 입장에서 \(A\)와 \(B\)도 서로 반대편이어야 한다.

두 조건이 모두 성립하면 교차합니다. 즉

$$ \text{ccw}(A,B,C)\cdot\text{ccw}(A,B,D) < 0 \quad\text{및}\quad \text{ccw}(C,D,A)\cdot\text{ccw}(C,D,B) < 0 $$

까다로운 경계 — 일직선/끝점 닿음

위 곱이 0이 되는 경우(어떤 ccw가 0 = 세 점 일직선)는 별도 처리해야 합니다.
한 선분의 끝점이 다른 선분 위에 닿거나, 두 선분이 일부 겹치는 경우입니다.
이때는 구간 겹침 검사(좌표 범위가 겹치는지)를 추가합니다.

핵심 직관

복잡해 보이는 기하 판정이 결국 외적 부호 몇 개의 조합 으로 환원됩니다.
나눗셈이나 기울기를 쓰지 않아 0으로 나누기·부동소수 오차를 피할 수 있다는
점도 큰 장점입니다. 다음 강의에서 정수 안전 구현과 경계 처리를 봅니다.

CCW 구현 (C++) — 정수로 안전하게

좌표가 정수면 외적도 정수라 부동소수 오차가 전혀 없습니다.

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

struct P { ll x, y; };

// 양수: 반시계, 음수: 시계, 0: 일직선
ll ccw(P a, P b, P c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int sign(ll v) { return (v > 0) - (v < 0); }

좌표가 최대 \(10^9\)이면 차의 곱이 약 \(10^{18}\sim4\times10^{18}\)까지 커집니다.
반드시 long long (경우에 따라 __int128)으로 받아야 오버플로가 없습니다.
이것이 이 단원의 1순위 함정입니다.

선분 교차 판정 (C++) — 경계 포함

bool onSeg(P a, P b, P c) {        // 일직선일 때 c가 [a,b] 위인가
    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 intersect(P a, P b, P c, P d) {
    int ab = sign(ccw(a, b, c)) * sign(ccw(a, b, d));
    int cd = sign(ccw(c, d, a)) * sign(ccw(c, d, b));
    if (ab == 0 && cd == 0) {       // 네 점이 일직선 — 구간 겹침 검사
        if (a.x > b.x || (a.x == b.x && a.y > b.y)) swap(a, b);
        if (c.x > d.x || (c.x == d.x && c.y > d.y)) swap(c, d);
        return onSeg(a, b, c) || onSeg(a, b, d)
            || onSeg(c, d, a) || onSeg(c, d, b)
            || !(b.x < c.x || d.x < a.x
                 || (b.x == c.x && b.y < c.y) /* 정렬 비교 */);
    }
    return ab <= 0 && cd <= 0;       // 끝점 닿음(=0)도 교차로 포함
}

ab <= 0 && cd <= 0은 "끝점이 다른 선분에 닿는 경우"까지 교차로 칩니다.
끝점 닿음을 교차로 안 칠지(엄격 교차)는 문제 정의에 맞춰 < 0으로 바꿉니다.
일직선 케이스는 좌표를 정렬해 구간이 겹치는지로 판정합니다.

파이썬 구현 (핵심부)

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

def sign(v):
    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]))

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

흔한 함정

• 오버플로 — C++에서 좌표가 크면 long long/__int128. 가장 자주 틀림.
• 일직선(=0) 미처리 — ccw == 0인 공선/끝점 닿음을 빼먹으면 경계 케이스
  오답. 곱의 부호만 보면 0을 놓칩니다.
• 부동소수 사용 — 가능하면 정수로. 기울기·나눗셈은 0 분모와 오차를 부릅니다.
• 끝점 포함 여부 — "닿음을 교차로 보는가"를 문제에서 명확히 하고 <=/<
  선택.

응용 패턴

• 볼록 껍질(그라함 스캔/모노톤 체인) — 회전 방향을 ccw로 판정해 후퇴.
• 다각형 안/밖 판정 — 반직선과 변들의 교차 횟수, 또는 ccw 부호 일관성.
• 다각형 넓이 — 신발끈 공식(외적의 합 / 2).
• 점들의 정렬(각도 정렬) — ccw를 비교자로 사용해 나눗셈 없이 정렬.
• 선분들의 교차 존재(스위프 라인) — ccw 판정을 부품으로.

외적 부호 하나가 방향·넓이·좌우 판정을 모두 담는다는 사실이 기하의 출발점
입니다. 정수로 계산해 오차를 없애는 습관까지 들이면 기하 문제가 한결
안정적으로 풀립니다.

출제 신호

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

풀이 결정 절차

1. 필요한 판정을 CCW(외적 부호)로 번역합니다 —
   \(\text{ccw}(A, B, C) = (B-A) \times (C-A)\)의 부호가 +면 반시계, \(-\)면 시계,
   0이면 일직선.
2. 교차 판정이면 표준 2단계를 씁니다 — (a) 서로를 기준으로 CCW 부호가
   엇갈리면 교차, (b) 둘 다 0이 나오는 일직선 케이스는 따로 처리.
3. 좌표 최대값을 보고 자료형을 정합니다 — \(|x| \le 10^9\)이면 외적 항이
   \(\approx 4 \times 10^{18}\) 근처까지 가므로 long long이 경계선입니다.
   \(10^9\)를 넘으면 __int128 또는 파이썬.
4. "끝점에서 닿는 것도 교차인가?"를 문제에서 확인합니다 — 포함이면 등호( \(\ge\),
   \(\le\) )가 판정식에 들어가야 합니다.

자주 하는 실수

1순위는 압도적으로 오버플로입니다. 좌표가 \(10^9\)면 차이가 \(2 \times 10^9\),
외적은 그 곱이라 int는 물론 곱셈 중간값이 long long도 위협합니다.

using ll = long long;
int ccw(ll ax, ll ay, ll bx, ll by, ll cx, ll cy) {
    ll t = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);  // 전부 ll 로
    return (t > 0) - (t < 0);     // 값이 아니라 부호만 돌려준다
}

부호만 반환하는 습관이 중요합니다 — 이후 비교에서 또 곱하다 넘치는 사고를
원천 차단합니다.

• 일직선(공선) 케이스 누락 — 네 CCW가 모두 0이면 두 선분이 같은 직선
  위에 있습니다. 이때는 좌표 구간이 겹치는지(1차원 겹침 검사)로 판정해야
  합니다. 점 비교는 (x, y) 사전순으로 양 끝을 정규화한 뒤
  max(A1, B1) <= min(A2, B2) 형태로.

def segments_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 max(a, c) <= min(b, d)
    return ab <= 0 and cd <= 0               # 끝점 접촉 포함이면 <=

• 부등호 방향 — 끝점 접촉을 교차로 안 치는 문제면 < 0(엄격)으로
  바꿔야 합니다. 문제 정의 한 줄로 등호가 갈립니다.
• 실수 기하로 도피 — 기울기 비교나 교점 좌표 계산으로 풀면 수직선
  (기울기 무한대)과 부동소수 오차에 당합니다. 정수 입력은 끝까지 정수로.
• 퇴화 선분(길이 0) — 같은 점 두 개로 이루어진 입력이 가능한 문제가
  있습니다. 점-선분 포함 판정으로 별도 처리하세요.

연습 방법

사이드바 연습 목록은 CCW 단독 판정 → 교차 여부(접촉 불포함) → 접촉·공선
포함 교차 → 교점 좌표/응용 순으로 난도가 올라가도록 배치되어 있습니다.
특히 공선 케이스가 있는 문제에서 직접 반례(겹치는 구간, 한 점 접촉, 떨어진
공선)를 만들어 자기 코드로 검증해 보는 연습이 가장 효과적입니다. 태그된
문제 3문제 이상 해결 시 마스터 처리되어 레이팅 CLASS 보너스에
반영됩니다.