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

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

직사각형

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

요약
N개의 축에 평행한 직사각형이 주어질 때, 합집합의 넓이를 구한다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 정렬, 누적 합
정답자
아직 제출이 없습니다

문제

좌표축에 평행한 변을 가진 직사각형 NN개가 평면 위에 놓여 있다. 이 직사각형들이 덮는 영역의 전체 넓이를 구하는 프로그램을 작성하시오. 여러 직사각형이 겹쳐서 덮는 영역이라도 넓이는 한 번만 센다.

입력

첫째 줄에 양의 정수 NN이 주어진다. (1≤N≤200,0001 \le N \le 200{,}000)

다음 NN개의 줄에는 각각 공백으로 구분된 네 정수 x1x_1, x2x_2, y1y_1, y2y_2가 주어지며, 이는 직사각형 [x1,x2]×[y1,y2][x_1, x_2] \times [y_1, y_2]를 나타낸다.

모든 좌표는 정수이고 0≤x1<x2≤1090 \le x_1 < x_2 \le 10^9, 0≤y1<y2≤1090 \le y_1 < y_2 \le 10^9를 만족한다.

출력

첫째 줄에 NN개의 직사각형이 덮는 영역의 전체 넓이를 출력한다.

예제2

  1. 예제 1

    입력
    2
    0 3 1 2
    1 2 0 3
    
    예상 출력
    5
    
  2. 예제 2

    입력
    1
    0 5 0 4
    
    예상 출력
    20