Geometry Basic: 벡터, CCW, 외적, 내적

정의

기하 알고리즘의 밑바탕. 대부분의 2D/3D 기하 문제는 벡터 연산, 내적/외적, CCW 판정 세 가지의 조합으로 풀립니다.

문제 상황

PS 기하에서 자주 마주치는 질문들:

• 두 선분이 교차하는가? (선분 교차 판정)
• 점이 다각형 내부에 있는가? (Point-in-Polygon)
• 볼록 껍질의 넓이를 구하라 (Convex Hull + Shoelace)
• N개 선분 중 교차하는 쌍이 있는가? (Sweep Line + CCW)
• 세 점의 회전 방향은? (삼각형 넓이의 부호)

왜 어려운가: 부동소수점 오차와 정수 오버플로 두 함정이 동시에 존재. 좌표가 정수라면 외적/내적을 정수로만 계산해 완전히 정확한 판정이 가능하다.

벡터

2D 벡터: 두 점 $A=(a_x,a_y)$ 와 $B=(b_x,b_y)$ 사이의 방향/거리 표현.

struct Vec { long long x, y; };

Vec sub(Vec a, Vec b) { return {a.x - b.x, a.y - b.y}; }
Vec add(Vec a, Vec b) { return {a.x + b.x, a.y + b.y}; }

long long dot(Vec a, Vec b)   { return a.x*b.x + a.y*b.y; }
long long cross(Vec a, Vec b) { return a.x*b.y - a.y*b.x; }

내적 (Dot Product)

용도:

• 각도: \cos\theta = \frac\{\vec{a} \cdot \vec{b}\}\{|\vec{a}||\vec{b}|\}
• 직교 판정: $\overrightarrow{\{}a\}\cdot \overrightarrow{\{}b\}=0$ ⟺ 수직
• 투영: $\overrightarrow{\{}a\}$ 를 $\overrightarrow{\{}b\}$ 방향으로 투영한 길이 = \frac\{\vec{a} \cdot \vec{b}\}\{|\vec{b}|\}

외적 (Cross Product), 핵심 도구

2D 에서 외적은 스칼라 (z 성분만):

부호 의미:

절댓값 의미: $\overrightarrow{\{}a\}$, $\overrightarrow{\{}b\}$ 가 이루는 평행사변형의 넓이. 삼각형이면 이의 절반.

CCW (Counterclockwise Test)

세 점 $A,B,C$ 의 방향 관계 판정. 알고리즘 기하의 만능 도구입니다.

int ccw(Vec a, Vec b, Vec c) {
    long long v = cross(sub(b, a), sub(c, a));
    return (v > 0) - (v < 0);  // 1, -1, 0
}

해석:

응용은 광범위: convex hull, 선분 교차, 다각형 내부 판정, 회전 캘리퍼스 등 거의 모든 기하 알고리즘의 기본 연산.

CCW 시각화

graph LR
    subgraph CCW["CCW = +1 (반시계)"]
        A1[A] --> B1[B]
        B1 --> C1[C]
        C1 -.-> A1
    end
    subgraph CW["CCW = -1 (시계)"]
        A2[A] --> B2[B]
        B2 --> C2[C]
        C2 -.-> A2
    end
    subgraph Colinear["CCW = 0 (일직선)"]
        A3[A] --- B3[B] --- C3[C]
    end

선분 교차

두 선분 $AB$ 와 $CD$ 가 교차하는지 판정:

bool segments_intersect(Vec a, Vec b, Vec c, Vec d) {
    int d1 = ccw(a, b, c);
    int d2 = ccw(a, b, d);
    int d3 = ccw(c, d, a);
    int d4 = ccw(c, d, b);

    if (d1 != d2 && d3 != d4) return true;  // 일반 교차

    // 특수: 한 선분이 다른 선분의 끝점을 지나는 경우
    if (d1 == 0 && on_segment(a, b, c)) return true;
    if (d2 == 0 && on_segment(a, b, d)) return true;
    if (d3 == 0 && on_segment(c, d, a)) return true;
    if (d4 == 0 && on_segment(c, d, b)) return true;
    return false;
}

bool on_segment(Vec a, Vec b, Vec 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);
}

### 선분 교차 판정 흐름

```mermaid
flowchart TD
    A["두 선분 AB, CD"] --> B["d1..d4 계산"]
    B --> C{"일반 교차 성립?"}
    C -->|"Yes"| YES["교차 true"]
    C -->|"No"| D{"끝점이 선분 위?"}
    D -->|"Yes"| YES
    D -->|"No"| NO["비교차 false"]

삼각형/다각형 넓이

삼각형 $A,B,C$ 의 넓이:

다각형 (Shoelace formula): 정점 $P_0,P_1,...,P_{n-1}$ 에 대해

다각형 내부 점 판정

Ray casting: 점에서 임의 방향으로 반직선을 그어 다각형 변과 몇 번 교차하는지 세기.

• 홀수 → 내부
• 짝수 → 외부

또는 winding number: 모든 변에서 CCW 부호를 세어 총합을 봄. 이쪽이 볼록 다각형에서 더 간단.

구현 예시

Shoelace 공식으로 다각형 넓이를 구하는 구현. 정수 좌표에서 넓이의 2배를 long long 으로 정확히 계산한 뒤 출력한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct P { ll x, y; };

ll area2(vector<P>& pts) {
  int n = pts.size();
  ll res = 0;
  for (int i = 0; i < n; i++) {
      int j = (i + 1) % n;
      res += pts[i].x * pts[j].y;
      res -= pts[j].x * pts[i].y;
  }
  return abs(res);
}

int main() {
  int n; cin >> n;
  vector<P> pts(n);
  for (auto& p : pts) cin >> p.x >> p.y;
  ll a2 = area2(pts);
  cout << a2 / 2;
  if (a2 % 2 == 1) cout << ".5";
  else cout << ".0";
  cout << endl;
}

import sys
input = sys.stdin.readline

n = int(input())
pts = [tuple(map(int, input().split())) for _ in range(n)]

a2 = 0
for i in range(n):
  j = (i + 1) % n
  a2 += pts[i][0] * pts[j][1] - pts[j][0] * pts[i][1]

a2 = abs(a2)
half = a2 // 2
print(f"{half}.5" if a2 % 2 else f"{half}.0")

3
0 0
3 0
0 4

6.0

4
0 0
4 0
4 3
0 3

12.0

복잡도

함정

• 정밀도: double 로 외적 계산은 위험. 정수 좌표 → long long 이 원칙.
• 오버플로: 좌표가 $10^9$ 이상이면 곱셈 후 $10^{18}$ 넘을 수 있음. __int128 또는 좌표 축소.
• 일직선 케이스: CCW=0 일 때 하위 로직 (on-segment 등) 을 반드시 처리해야 함. 잊으면 교차 판정 등이 오동작.
• 각도 비교: atan2 는 double, 정밀도 문제 있음. 정수 좌표에서 각도 정렬은 사분면 + 외적으로 처리.

BOJ 연습 문제

참고

• 관련 Shoelace, 다각형 넓이
• 관련 Convex Hull (CCW 로 구현)
• 관련 Rotating Calipers
• cp-algorithms: Basic Geometry