Lesson 213. 기하 알고리즘
Geometry: Vectors, Cross Product, Segment Intersection, Polygon Area, and Convex Hull
- CCW(Counter-Clockwise)를 이용한 세 점의 방향 판정
- 외적 부호와 경계 조건(Segment Check)을 이용한 선분 교차 판정
- 신발끈 공식을 활용한 임의의 다각형 넓이 산출
- $x$축 정렬과 스택을 이용한 모노톤 체인 볼록 껍질 탐색
수업 목표 및 핵심 역량
- 좌표 공간 상 두 벡터의 회전 방향을 부동소수점 오차 없이 정확히 판별합니다.
- 선분 교차 시 일직선 상에 두 선분이 놓이는 경계 예외를 완벽히 통제합니다.
- 꼭짓점 순회로 다각형의 넓이를 $O(N)$에 실수 연산 유실 없이 계산합니다.
- $N$개의 임의의 점 중 최외곽 껍질을 구성하는 정점들을 $O(N \log N)$에 빌드합니다.
외적 CCW 방향 판정
- 두 벡터의 $z$축 외적 성분 부호 검출
# 8065번: 방향 판정 발췌
# (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)
val = ccw(a, b, c)
direction = 1 if val > 0 else (-1 if val < 0 else 0)
선분 교차 판정
- CCW 곱 조건 및 일직선 상 겹침(on segment) 체크
# 8066번: 선분 교차 판정 발췌
if abc * abd < 0 and cda * cdb < 0:
return True
if abc == 0 and on_segment(c, a, b): return True
# ... 나머지 세 점 일직선 상 체크 반복
다각형 넓이 (Shoelace)
- 정수 누적 후 최종 소수 변환을 통한 정밀도 확보
# 8067번: 다각형의 넓이 발췌
for i in range(n):
j = (i + 1) % n
area2 += x[i]*y[j] - x[j]*y[i]
area = abs(area2) / 2.0
볼록 껍질 (Monotone Chain)
- 정렬 후 CCW 검사로 우회전(ccw <= 0)하는 점들을 제거하여 껍질 확보
# 8068번: 볼록 껍질 발췌
lower = []
for p in pts:
while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
오류 예방 및 안정성 체크
- **Int64 자료형 필수화**: 좌표 값 $10^9$의 곱 계산 시 반드시 64비트 정수 연산을 보장하여 정수 오버플로우 배제
- **나눗셈 연산의 뒤로 늦춤**: 사선 공식 연산 시 나누기 2는 계산 중간이 아닌 출력 바로 직전에 수행해 누적 오차 완전 제거
- **일직선 겹침 경계 추가**: 선분 교차 판단 시 CCW가 0인 일직선 상태는 x, y 좌표 범위 겹침(on_segment)을 추가 조사