직사각형 교집합

면접 대비

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

요약

n개의 축에 평행한 직사각형이 모두 겹치는 영역의 넓이를 구하고 겹치는 부분이 없으면 0을 출력합니다.

문제

직사각형 $n$ 개로 이루어진 집합 $\{R_1, R_2, \ldots, R_n\}$ 이 주어진다. 모든 직사각형이 함께 덮는 부분의 넓이 $\mathrm{Area}(R_1 \cap R_2 \cap \cdots \cap R_n)$ 을 구하라.

$R_1, R_2, \ldots, R_n$ 의 변은 모두 수평이거나 수직이다.

아래 그림에서 직사각형 $R_1$ , $R_2$ , $R_3$ , $R_4$ 의 교집합은 색칠한 직사각형이다.

첫째 줄에 직사각형의 개수 $n$ 이 주어진다. ( $1 < n < 1000$ )

각 직사각형의 변은 $x$ 축과 $y$ 축에 평행하므로 직사각형 하나는 네 직선 $x = x_1$ , $x = x_2$ , $y = y_1$ , $y = y_2$ 로 둘러싸인다. 둘째 줄부터 $n$ 개 줄에 직사각형 하나씩을 다음 형식으로 준다.

x1 x2 y1 y2

$x_1$ , $x_2$ , $y_1$ , $y_2$ 는 정수이고 $0 \le x_1 < x_2 \le 10000$ , $0 \le y_1 < y_2 \le 10000$ 이다.

모든 직사각형의 교집합의 넓이를 출력한다. 교집합이 비어 있으면 0을 출력한다.