쿠키 부스러기

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

요약

직사각형 쿠키와 최대 100개의 닫힌 직사각형 칩이 주어질 때, 칩을 제거한 뒤 남는 연결 조각의 수를 센다.

난이도: 보통10점 중 7점
유형: 기하, 유니온 파인드, 조합론
정답자: 아직 제출이 없습니다

문제

쿠키 몬스터는 직사각형 모양의 쿠키를 굽고, 그 위에 직사각형 초코칩을 여러 개 박아 넣습니다. 오븐 온도를 너무 높이는 바람에 모든 초코칩이 녹아 흘러나가고, 초코칩이 있던 자리에는 정확히 그 모양의 구멍이 남습니다. 이렇게 구멍이 뚫리면 쿠키가 서로 떨어진 여러 조각으로 갈라질 수 있는데, 이 조각들을 부스러기라고 부릅니다.

각 초코칩은 각 변이 좌표축에 평행한 직사각형이며, 닫힌 영역으로 취급합니다. 즉 자신의 둘레(경계선) 위의 점들도 포함합니다. 따라서 한 점(모서리)에서만 맞닿는 두 쿠키 조각은, 공유하는 그 모서리 점이 초코칩과 함께 사라지므로 서로 다른 부스러기로 셉니다.

쿠키와 모든 초코칩이 주어질 때, 초코칩이 모두 녹은 뒤 남는 부스러기가 몇 개인지 세세요.

입력

첫째 줄에 네 정수 x1 y1 x2 y2가 주어집니다. 각 값은 $-10^9$ 이상 $10^9$ 이하이며, 쿠키의 마주 보는 두 꼭짓점 좌표입니다. 쿠키는 각 변이 좌표축에 평행한 직사각형입니다.

둘째 줄에 초코칩의 개수 n이 주어집니다 ( $0 \le n \le 100$ ).

다음 n개의 줄에는 각각 네 정수 x1 y1 x2 y2가 주어지며, 각 값은 $-10^9$ 이상 $10^9$ 이하로 한 초코칩의 마주 보는 두 꼭짓점 좌표입니다. 모든 초코칩은 각 변이 좌표축에 평행한 직사각형입니다.

초코칩끼리는 서로 겹칠 수 있고, 쿠키의 일부 또는 전체 바깥에 걸쳐 있을 수도 있습니다. 쿠키와 모든 초코칩의 넓이는 0이 아닙니다. 각 초코칩은 자신의 둘레 위의 점들을 포함합니다.

출력

모든 초코칩이 녹아 사라진 뒤 쿠키가 갈라지는 부스러기(연결된 조각)의 개수를 정수 하나로 출력하세요.

예제3

예제 1

입력

0 0 100 100
2
0 0 50 50
50 50 100 100

예상 출력

예제 2
입력
```
0 0 10 10
0
```
예상 출력
```
1
```
예제 3
입력
```
0 0 10 10
1
-5 -5 15 15
```
예상 출력
```
0
```