행사장 대여 (Small)

면접 대비

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

요약

최대 100개의 축에 평행한 직사각형이 주어질 때, 모든 직사각형의 합집합 넓이를 구한다.

난이도: 보통10점 중 4점
유형: 배열, 구현, 시뮬레이션, 기하
정답자: 아직 제출이 없습니다

문제

상현이는 입대를 앞두고 이별 파티를 열려고 한다. 파티를 치를 행사장을 대여하는데, 이 업체는 전직 프로그래머만 일해서 대여 방식이 독특하다.

상현이가 빌릴 장소를 정하면 업체는 그 장소를 남김없이 덮는 직사각형 $N$ 개를 만든다. 그리고 직사각형의 개수 $N$ 과 각 직사각형의 좌측 하단 좌표, 우측 상단 좌표를 알려준다. $N$ 개의 직사각형은 일부만 겹칠 수도 있고 완전히 겹칠 수도 있다. 모든 직사각형의 변은 좌표축과 평행하다.

상현이가 빌린 행사장의 넓이, 즉 $N$ 개의 직사각형 중 적어도 하나가 덮는 영역의 넓이를 구하는 프로그램을 작성하라.

입력

첫째 줄에 직사각형의 개수 $N$ ( $2 \le N \le 100$ )이 주어진다.

이어지는 $N$ 개의 줄에 네 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ ( $0 \le x_1 < x_2 \le 500$ , $0 \le y_1 < y_2 \le 500$ )가 공백으로 구분되어 주어진다. 각 직사각형의 좌측 하단 좌표는 $(x_1, y_1)$ 이고, 우측 상단 좌표는 $(x_2, y_2)$ 이다.

출력

첫째 줄에 상현이가 빌린 행사장의 넓이를 출력한다. 넓이는 항상 정수이므로 소수점 없이 출력한다.

예제6

예제 1
입력
```
3
4 2 6 3
4 0 5 1
0 0 7 8
```
예상 출력
```
56
```
예제 2
입력
```
2
0 0 2 2
5 5 7 7
```
예상 출력
```
8
```
예제 3
입력
```
2
1 1 4 4
1 1 4 4
```
예상 출력
```
9
```
예제 4
입력
```
2
0 0 4 4
2 2 6 6
```
예상 출력
```
28
```
예제 5
입력
```
2
0 0 3 3
3 0 6 3
```
예상 출력
```
18
```
예제 6
입력
```
2
0 0 500 500
0 0 500 500
```
예상 출력
```
250000
```