목이 쉰 말

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

요약

평면 위의 선분들이 주어질 때, 이들이 둘러싸는 유계 영역의 최대 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 그래프, DFS, 구현
정답자: 아직 제출이 없습니다

문제

농부 밥의 말이 전부 목이 쉬었고, 감기에 걸렸을지도 모른다. 조랑말마저 목이 조금 쉬었다. 그래서 농장의 동물을 한 마리씩 따로 격리해야 한다. 동물을 떼어 놓으려고 밥은 어떤 동물도 넘어갈 수 없는 울타리 $n$ 개를 마련해 두었다. 그런데 농부 앨리스가 그 울타리를 전부 가져다가 평면에 아무렇게나 늘어놓았다. 밥에게는 울타리를 다시 배치할 시간이 없으니 놓인 그대로 써야 한다.

밥이 격리할 수 있는 동물이 최대 몇 마리인지 구하라. 울타리로 둘러싸이고 내부가 비어 있지 않은 영역에 동물을 최대한 많이 넣되, 어떤 동물도 다른 동물이 있는 곳까지 갈 수 없어야 하고 무한히 먼 곳으로 빠져나갈 수도 없어야 한다.

울타리 하나는 두 점을 잇는 선분이다. 세 울타리가 한 점에서 만나는 경우는 없고, 두 울타리가 점 하나보다 넓은 부분을 함께 지나는 경우도 없다. 울타리끼리 서로 가로지르는 것은 허용된다.

입력

첫 줄에 울타리의 개수 $n$ 이 주어진다. ( $1 \le n \le 1000$ )

이어지는 $n$ 개 줄에 각각 정수 네 개 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 주어진다. ( $-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$ ) 울타리는 두 끝점 $(x_1, y_1)$ 과 $(x_2, y_2)$ 를 잇는 선분이고, 두 끝점은 서로 다르다.

출력

밥이 격리할 수 있는 동물의 최대 마리 수 $c$ 를 한 줄에 출력한다.

힌트

세 번째 예제 입력을 그린 그림이다. 세로 울타리 두 개와 가로 울타리 두 개, 대각선 울타리 하나가 영역 네 개를 만든다.

예제3

예제 1
입력
```
1
1 1 1 2
```
예상 출력
```
0
```
예제 2
입력
```
4
1 0 1 5
4 0 4 5
0 1 5 1
0 4 5 4
```
예상 출력
```
1
```

예제 3

입력

예상 출력