네 직사각형의 합집합 면적 구하기

면접 대비

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

요약

축에 평행한 네 개의 사각형이 주어질 때 이들이 덮는 영역의 전체 합집합 면적을 구합니다.

문제

평면 위에 네 개의 직사각형이 놓여 있다. 각 직사각형의 밑변과 윗변은 x축에 평행하다.

직사각형들은 서로 떨어져 있을 수도 있고, 일부 또는 전체가 겹칠 수도 있으며, 한 직사각형이 다른 직사각형을 포함할 수도 있다. 변이나 꼭짓점만 맞닿는 경우도 있다.

네 직사각형 중 하나 이상이 덮고 있는 부분의 전체 면적을 구하시오.

입력은 총 네 줄이다. 각 줄에는 한 직사각형을 나타내는 네 정수 x1, y1, x2, y2가 공백으로 구분되어 주어진다.

(x1, y1)은 왼쪽 아래 꼭짓점, (x2, y2)는 오른쪽 위 꼭짓점을 나타낸다. 모든 x좌표와 y좌표는 1 이상 100 이하의 정수이다.

네 직사각형이 차지하는 전체 면적을 첫 줄에 출력한다.