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

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

잔디 과다 심기

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

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

보통10점 중 7점

유형
기하, 정렬, 누적 합
정답자
아직 제출이 없습니다

문제

농부 존(Farmer John)은 농장에서 축에 평행한(즉, 변이 수직·수평인) 임의의 직사각형 영역에 잔디를 심을 수 있는 새 기계를 구입했다. 그런데 어느 날 기계가 고장 나서, 잔디를 한 곳이 아니라 서로 겹칠 수도 있는 NN개(1≤N≤10001 \le N \le 1000)의 서로 다른 직사각형 영역에 심어 버렸다.

잔디가 심긴 직사각형 영역들이 주어질 때, 농장에서 잔디로 덮인 전체 넓이를 구하여라.

입력

  • 첫째 줄: 정수 NN.
  • 둘째 줄부터 N+1N + 1번째 줄까지: 각 줄에는 네 정수 x1x_1 y1y_1 x2x_2 y2y_2가 공백으로 구분되어 주어진다. 이는 왼쪽 위 꼭짓점이 (x1,y1)(x_1, y_1)이고 오른쪽 아래 꼭짓점이 (x2,y2)(x_2, y_2)인 직사각형 영역을 나타낸다. 모든 좌표는 −108…108-10^8 \ldots 10^8 범위이다.

출력

  • 첫째 줄: 잔디로 덮인 전체 넓이. 이 값은 32비트 정수 범위를 넘을 수 있음에 유의하라.

예제1

  1. 예제 1

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