BOJ 1428 다각형의 개수

문제 링크:

문제 내용

$N$ 개의 직선이 주어집니다. 이 직선들이 이루는 유한한 영역의 개수를 구하시오.

입력

첫 줄에 $N$ 이 주어집니다. ( $1 \le N \le 50$ )

다음 $N$ 줄에 각각의 직선이 지나는 두 개의 점의 좌표가 $x_1$ , $y_1$ , $x_2$ , $y_2$ 의 순서로 주어집니다. ( $-10\;000 \le x_1, y_1, x_2, y_2 \le 10\;000$ , 모두 정수)

같은 직선이 여러 개 주어지지 않으며, 한 직선이 지나는 두 개의 점의 좌표가 같은 경우도 주어지지 않습니다.

출력

문제의 정답을 출력합니다.

문제 풀이

스포일러

Euler characteristic을 이용하는 풀이가 가능합니다. 어떤 평면 그래프에서 정점의 개수를 $v$ , 간선의 개수를 $e$ , 영역의 개수를 $f$ 라고 하면, $v - e + f = 1$ 이 성립하며, 이는 무한히 뻗어나가는 간선이 있는 경우에도 성립합니다.

이제 각 직선의 교점을 구하여 $v$ 와 $e$ 를 구할 수 있습니다. 두 직선이 한 점에서 만날 경우 $v$ 에 1을, $e$ 에 2를 더해 줍니다. 그리고 그 점에서 다른 직선이 또 만날 경우, 직선 하나 당 $e$ 에만 1을 더해 줍니다. 이때 같은 직선 쌍을 중복해 처리하지 않도록 합니다. 한 점에서 $k$ 개의 직선이 만날 경우 $\frac{k(k-1)}{2}$ 개의 쌍을 모두 방문 처리해야 합니다.

마지막으로, $f = 1 - v + e$ 로 영역의 개수를 구합니다. 여기서 무한 영역의 개수를 빼야 하는데, 직선이 $n$ 개이고 모두 평행하지 않을 경우 무한 영역은 $2n$ 개, 모두 평행이면 $n+1$ 개임을 보일 수 있습니다.

Last updated on 2025년 10월 8일 13:01:54

BOJ 14255 멋진 배열 BOJ 14314 Sherlock and Parentheses (Small)