수업 목표

본 수업은 평면 상의 좌표와 기하학적 형상을 수식으로 정의하고, 소수점 실수 연산 오차 없이 완벽한 기하 알고리즘을 설계하고 파이썬으로 구현할 수 있는 역량을 배양하는 것을 목표로 합니다. - 세 점의 좌표 관계를 규명하는 벡터 외적(CCW) 판정식을 이해하고, 시계/반시계/일직선 방향을 판별하는 함수를 올바르게 작성합니다. - CCW 관계 분석을 연장하여 두 선분의 교차 여부를 판별하고, 평행 및 일직선 상의 겹침과 같은 모든 기하학적 예외 상황을 처리하는 예외 처리 능력을 기릅니다. - 다각형 꼭짓점의 순차 좌표를 이용하여 신발끈 공식을 통해 넓이를 $O(N)$에 연산하는 기법을 구현합니다. - 수많은 평면 점 집합을 감싸는 가장 작은 볼록 다각형 껍질을 Monotone Chain 알고리즘을 사용하여 $O(N \log N)$에 구하는 껍질 탐색법을 구현합니다.

학습 동기부여

자율주행 자동차의 라이다(LiDAR) 센서 장애물 감지, 모바일 3D 게임 엔진의 오브젝트 충돌 감지(Collision Detection), 컴퓨터 그래픽스 렌더링, 그리고 카카오맵이나 네이버 지도 같은 GIS 시스템 상의 다각형 구역 영역 설정 등 현대 산업의 고난도 그래픽스/공간 시스템은 좌표 기하 알고리즘을 근간으로 작동합니다. 미세한 실수 연산의 한계로 인한 오류(Precision error)는 충돌 감지 실패나 그래픽 뭉개짐 같은 시스템 불안정을 야기합니다. 본 단원에서 배우는 정밀 기하 연산 기법들은 이러한 계산상 예외와 실수 연산의 오차를 논리적으로 무력화하고 완벽한 물리적 안정성을 제공하는 기하학적 최적화 도구들입니다.

도입 스토리

기상 관측을 위해 넓은 대양에 수천 개의 부표 센서가 둥둥 떠다니고 있습니다. 태풍이 올 때 이 센서들을 모두 포함하는 가장 외곽의 기상 감시 안전 구역(볼록 껍질)을 설정하려고 합니다. 만일 수천 개의 점을 직관적으로 하나씩 대조한다면 엄청난 연산량이 필요하겠지만, 점들을 왼쪽부터 정렬하여 아래 껍질과 위 껍질을 방향 검사(CCW)로 차곡차곡 쌓아나가는 기하학적 탐색 기법을 적용하면 단 $0.005$초 만에 안전 구역의 경계점을 찾아 고무줄로 감싸듯 완벽한 최소 볼록 다각형 영역을 얻어낼 수 있습니다. 평면의 신비로운 좌표 속에서 안전 경계를 구축하는 기하 알고리즘을 함께 학습해 봅시다.

1. 방향 판정 (CCW)

평면 상의 세 점 $A, B, C$가 이루는 방향 관계를 규명하는 가장 핵심적인 연산이 CCW(Counter-Clockwise)입니다. 벡터 $\vec{AB}$와 $\vec{AC}$의 외적을 구하면 $ccw = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)$이 되며, 이 외적 값의 부호에 따라 방향이 결정됩니다.

# 8065번: 방향 판정 — CCW 방향 식별 O(1) 알고리즘
import sys
input = sys.stdin.readline

def ccw(x1, y1, x2, y2, x3, y3):
    val = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
    if val > 0:
        return 1  # 반시계 방향 (Counter-Clockwise)
    elif val < 0:
        return -1 # 시계 방향 (Clockwise)
    return 0      # 일직선 (Collinear)

q = int(input())
for _ in range(q):
    x1, y1, x2, y2, x3, y3 = map(int, input().split())
    print(ccw(x1, y1, x2, y2, x3, y3))

2. 선분 교차 판정

두 선분 $AB$와 $CD$가 교차하려면, 선분 $AB$를 기준으로 점 $C$와 점 $D$가 서로 반대편에 있어야 하고($ccw(A, B, C) \cdot ccw(A, B, D) \le 0$), 동시에 선분 $CD$를 기준으로 점 $A$와 점 $B$도 반대편에 있어야 합니다. 단, 네 점이 모두 일직선 상에 존재하는 경우에는 선분의 좌표 범위가 겹치는지에 대한 개별 경계 조건을 검증해야 합니다.

# 8066번: 선분 교차 판정 — CCW 결합 교차 판정
import sys
input = sys.stdin.readline

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

def on_segment(p, a, b):
    return (p[0] >= min(a[0], b[0]) and p[0] <= max(a[0], b[0]) and
            p[1] >= min(a[1], b[1]) and p[1] <= max(a[1], b[1]))

def intersect(a, b, c, d):
    abc = ccw(a, b, c)
    abd = ccw(a, b, d)
    cda = ccw(c, d, a)
    cdb = ccw(c, d, b)
    
    if abc * abd < 0 and cda * cdb < 0:
        return True
    if abc == 0 and on_segment(c, a, b): return True
    if abd == 0 and on_segment(d, a, b): return True
    if cda == 0 and on_segment(a, c, d): return True
    if cdb == 0 and on_segment(b, c, d): return True
    return False

q = int(input())
for _ in range(q):
    ax, ay, bx, by, cx, cy, dx, dy = map(int, input().split())
    if intersect((ax, ay), (bx, by), (cx, cy), (dx, dy)):
        print(1)
    else:
        print(0)

3. 다각형의 넓이 (신발끈 공식)

다각형 꼭짓점의 좌표가 순서대로 주어질 때 다각형의 넓이는 신발끈 공식(사선 공식)을 사용하여 계산합니다. 좌표를 대각선 방향으로 서로 교차 곱셈하여 누적한 값의 절대 차이를 반으로 나눕니다.

# 8067번: 다각형의 넓이 — Shoelace Formula O(N) 알고리즘
import sys
input = sys.stdin.readline

def solve_area():
    n = int(input())
    pts = [list(map(int, input().split())) for _ in range(n)]
    
    area2 = 0
    for i in range(n):
        j = (i + 1) % n
        area2 += pts[i][0] * pts[j][1] - pts[j][0] * pts[i][1]
        
    area = abs(area2) / 2.0
    print(f"{area:.1f}")

solve_area()

4. 볼록 껍질 (Monotone Chain)

모노톤 체인(Monotone Chain) 알고리즘은 점들을 $x$좌표 기준으로 먼저 정렬한 뒤, 왼쪽 끝에서 오른쪽 끝으로 가며 아래쪽 껍질(Lower Hull)을 만들고, 역순으로 돌아오며 위쪽 껍질(Upper Hull)을 빌드하여 스택으로 다각형 경계를 감싸 나갑니다. $O(N \log N)$에 작동하여 점 개수가 수만 개인 경우에도 즉각 동작합니다.

# 8068번: 볼록 껍질 — Monotone Chain O(N log N) 알고리즘
import sys
input = sys.stdin.readline

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

def solve_convexhull():
    n = int(input())
    pts = [list(map(int, input().split())) for _ in range(n)]
    # x가 작은 순, 같으면 y가 작은 순 정렬
    pts = sorted(list(set(tuple(p) for p in pts)))
    
    if len(pts) < 3:
        print(len(pts))
        for p in pts:
            print(*p)
        return
        
    lower = []
    for p in pts:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
        
    upper = []
    for p in reversed(pts):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
        
    lower.pop()
    upper.pop()
    hull = lower + upper
    
    # 시작점 규칙 조정: y가 가장 작고, 같으면 x가 가장 작은 점을 첫 번째로
    start_idx = 0
    min_y, min_x = hull[0][1], hull[0][0]
    for i in range(1, len(hull)):
        if hull[i][1] < min_y or (hull[i][1] == min_y and hull[i][0] < min_x):
            min_y, min_x = hull[i][1], hull[i][0]
            start_idx = i
            
    sorted_hull = hull[start_idx:] + hull[:start_idx]
    
    print(len(sorted_hull))
    for p in sorted_hull:
        print(*p)

solve_convexhull()

자주 하는 실수 & 오류 예방

- 기하 좌표 곱셈 연산 오버플로우: 절댓값 $10^9$인 두 좌표를 곱하는 외적 계산($x_i y_{i+1}$) 시 계산 결과가 최대 $2 \cdot 10^{18}$에 달하므로 32비트 정수(Int)는 임계값을 가뿐히 초과합니다. 반드시 64비트 정수형(Int64 / Long Long / Python 대용량 정수)을 적용하여 오버플로우를 예방하십시오. - 실수 나누기 연산 조기 배제: 신발끈 공식이나 기하 거리 계산 시, 나누기를 조기 계산하여 소수로 누적하면 0.000001 수준의 부동 소수점 오차가 발생합니다. 2배 넓이를 정수로 온전히 더한 후, 최단 출력 직전에 단 한 번만 2.0으로 나누어 실수 오차를 방지하십시오. - 일직선 선분 교차 판단 오류: 네 점이 동일 선상에 놓여 교차할 때, 단순 방향 판정 부호 곱(CCW1 * CCW2 == 0) 조건만 두면 아예 닿지 않는 평행 분리 선분까지 교차(1)로 판단하게 됩니다. 경계 박스 조건(on_segment)을 추가하여 좌표 영역이 실제 맞닿는지 확인해야 통과됩니다.

핵심 정리

알고리즘 및 주제	시간 복잡도	공간 복잡도	주요 기하 원리	핵심 적용 분야
방향 판정 (CCW)	$O(1)$	$O(1)$	외적(Cross Product) 부호 판별	다각형 볼록성 검사, 회전 방향 제어
선분 교차 판정	$O(1)$	$O(1)$	상호 CCW 교차 조건 및 세 점 일직선 예외 처리	2차원 충돌 감지, 레이트레이싱 기초 연산
신발끈 넓이 공식	$O(N)$	$O(V)$	그린 정리(Green's Theorem) 이산 좌표 합산	지리 정보(GIS) 대지 면적 산출, 영역 측정
Monotone Chain	$O(N \log N)$	$O(V)$	좌표 정렬 후 스택 기반 좌회전(CCW > 0) 검사	클러스터링 외부 안전 경계선, 최외곽 부표 감싸기

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8065	방향 판정	CSES	쉬움	CCW 외적 계산
8066	선분 교차 판정	CSES	보통	CCW 조합 및 영역 예외 처리
8067	다각형의 넓이	CSES	보통	사선(신발끈) 공식 적용
8068	볼록 껍질	CSES	어려움	Monotone Chain 껍질 빌드