BOJ 1428 다각형의 개수
문제 내용
개의 직선이 주어집니다. 이 직선들이 이루는 유한한 영역의 개수를 구하시오.
입력
첫 줄에 이 주어집니다. ()
다음 줄에 각각의 직선이 지나는 두 개의 점의 좌표가 , , , 의 순서로 주어집니다. (, 모두 정수)
같은 직선이 여러 개 주어지지 않으며, 한 직선이 지나는 두 개의 점의 좌표가 같은 경우도 주어지지 않습니다.
출력
문제의 정답을 출력합니다.
문제 풀이
스포일러
Euler characteristic을 이용하는 풀이가 가능합니다. 어떤 평면 그래프에서 정점의 개수를 , 간선의 개수를 , 영역의 개수를 라고 하면, 이 성립하며, 이는 무한히 뻗어나가는 간선이 있는 경우에도 성립합니다.이제 각 직선의 교점을 구하여 와 를 구할 수 있습니다. 두 직선이 한 점에서 만날 경우 에 1을, 에 2를 더해 줍니다. 그리고 그 점에서 다른 직선이 또 만날 경우, 직선 하나 당 에만 1을 더해 줍니다. 이때 같은 직선 쌍을 중복해 처리하지 않도록 합니다. 한 점에서 개의 직선이 만날 경우 개의 쌍을 모두 방문 처리해야 합니다.
마지막으로, 로 영역의 개수를 구합니다. 여기서 무한 영역의 개수를 빼야 하는데, 직선이 개이고 모두 평행하지 않을 경우 무한 영역은 개, 모두 평행이면 개임을 보일 수 있습니다.