문제
격자평면 위에 직사각형이 n개 주어져 있다. 이 때, 모든 직사각형 합집합의 넓이를 구하여라.
입력
첫째 줄에 직사각형의 개수 n (1 ≤ n ≤ 200,000)이 주어진다.
다음 n개의 줄에 직사각형의 정보를 의미하는 수 x1, y1, x2, y2가 주어진다.
여기서 사각형의 왼쪽 아래 좌표는 (x1, y1)이고, 오른쪽 위 좌표는 (x2, y2)이다.
(0 ≤ x1 < x2 ≤ 106, 0 ≤ y1 < y2 ≤ 106)
출력
모든 직사각형의 합집합 넓이를 출력한다.
예제
7
0 10 20 20
10 18 35 25
30 6 39 24
15 4 31 14
17 25 25 32
45 20 51 30
49 10 55 26
819
로그인해야 코드를 작성할 수 있어요.