다각형 개수

시간 제한2초메모리 제한128 MB

요약
정수 좌표를 가진 최대 60개의 선분을 그렸을 때, 교차로 생긴 면이나 여분의 선분이 붙은 도형은 제외하고 단순 폐다각형의 개수를 구합니다.
난이도

어려움10점 중 8점

유형
기하, 그래프, 유니온 파인드
정답자
아직 제출이 없습니다

문제

정수 좌표로 주어진 선분들을 종이에 그렸을 때, 그 선분들만으로 만들어지는 다각형이 모두 몇 개인지 구하라.

여기서 다각형은 세 개 이상의 선분으로 이루어진 하나의 단순한 닫힌 도형을 뜻한다. 두 다각형이 서로 겹치거나 교차하면서 생기는 새로운 영역은 다각형으로 세지 않는다. 입력으로 주어진 선분들을 그대로 사용해 만들어지는 닫힌 도형만 다각형으로 인정한다.

또한 어떤 닫힌 도형에 그 도형을 이루지 않는 선분이 연결되어 있다면, 그 닫힌 도형은 다각형으로 보지 않는다.

입력

첫째 줄에 선분의 개수 N이 주어진다. 1 <= N <= 60이다.

다음 N개의 줄에는 각 선분의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 한쪽 끝점의 가로 좌표와 세로 좌표, 다른 쪽 끝점의 가로 좌표와 세로 좌표가 차례로 주어진다.

모든 좌표는 10000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 다각형의 개수를 출력한다.

예제1

  1. 예제 1

    입력
    23
70 160 100 200
60 60 70 160
100 120 130 130
90 70 140 110
70 160 70 110
70 110 120 90
70 160 120 140
120 140 120 90
90 70 100 120
130 130 140 110
60 60 110 140
110 140 160 80
150 160 160 80
120 170 160 80
120 140 150 140
140 90 160 120
160 120 170 130
170 130 190 120
200 80 220 50
200 80 230 110
220 90 230 110
220 90 230 80
220 50 230 80
    예상 출력
    2