아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

직사각형

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

요약
최대 1000개의 축에 평행한 직사각형이 겹치는 부분을 한 번만 세어 전체 덮인 넓이를 구합니다.
난이도

보통10점 중 6점

유형
정렬, 구간, 기하
정답자
아직 제출이 없습니다

문제

네 변이 좌표축과 평행한 직사각형은 대각선의 두 끝점만으로 언제나 정해진다. 예를 들어 왼쪽 위 좌표 (x1,y1)(x_1, y_1)과 오른쪽 아래 좌표 (x2,y2)(x_2, y_2)를 알면 직사각형 하나를 그릴 수 있다.

직사각형 여러 개가 주어졌을 때, 이 직사각형이 함께 덮는 전체 넓이를 구하려고 한다. 아래 그림에서 전체 넓이는 실선 안쪽 영역의 넓이다. 겹치는 부분은 두 번 세지 않는다.

직사각형 집합이 주어지면 모든 직사각형이 덮는 전체 넓이를 구하는 프로그램을 작성하시오.

입력

입력은 직사각형 NN개를 나타내고, NN은 0 이상 1000 이하다. 첫째 줄에 정수 NN이 주어진다. 이어지는 각 줄에는 직사각형 하나의 좌표가 정수 네 개 x1x_1, y1y_1, x2x_2, y2y_2로 주어지며, 두 점 (x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)를 뜻한다. 수와 수 사이는 공백 한 개 이상으로 구분한다. 이 두 점이 반드시 왼쪽 위와 오른쪽 아래인 것은 아니다. 모든 xix_i와 yiy_i는 0 이상 3276732767 이하다.

출력

첫째 줄에 직사각형이 덮는 전체 넓이를 출력한다. 넓이가 3276732767 이하라고 가정해도 된다.

예제1

  1. 예제 1

    입력
    4
    20 5 0 15
    37 26 14 9
    20040 2 20050 18
    17 22 33 15
    
    예상 출력
    715