행사장 대여 (Small)

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

보통4배열구현시뮬레이션기하면접 대비아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

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

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

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

입력

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

이어지는 NN개의 줄에 네 정수 x1x_1, y1y_1, x2x_2, y2y_2(0x1<x25000 \le x_1 < x_2 \le 500, 0y1<y25000 \le y_1 < y_2 \le 500)가 공백으로 구분되어 주어진다. 각 직사각형의 좌측 하단 좌표는 (x1,y1)(x_1, y_1)이고, 우측 상단 좌표는 (x2,y2)(x_2, y_2)이다.

출력

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