마법 격자의 넓이
골드 III의견: 0
왕국의 마법사가 \(N\)개의 직사각형 마법 격자를 격자 평면 위에 펼쳐 놓았다. 각 직사각형은 축에 평행하며 정수 좌표를 꼭짓점으로 가진다.
격자들이 서로 겹칠 수도 있다. 모든 직사각형의 합집합의 넓이를 구하여라.
- \(1 \le N \le 100\,000\)
- \(0 \le x_1 < x_2 \le 10^9\)
- \(0 \le y_1 < y_2 \le 10^9\)
첫째 줄에 직사각형의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 직사각형의 정보 \(x_1\ y_1\ x_2\ y_2\)가 공백으로 구분되어 주어진다. \((x_1, y_1)\)은 왼쪽 아래, \((x_2, y_2)\)는 오른쪽 위 꼭짓점을 나타내며 \(x_1 < x_2\), \(y_1 < y_2\)가 보장된다.
\(N\)개의 직사각형 합집합의 넓이를 출력한다.
2
0 0 3 2
1 1 4 3
10
두 직사각형의 합집합 넓이를 구한다. \((0,0)-(3,2)\)의 넓이 \(6\), \((1,1)-(4,3)\)의 넓이 \(6\), 겹치는 영역 \((1,1)-(3,2)\)의 넓이 \(2\)를 빼면 합집합 넓이는 \(10\)이다.
2
0 0 2 2
2 2 4 4
8
두 직사각형이 꼭짓점 하나만 공유한다. 각각 넓이 \(4\)이고 겹치는 넓이가 \(0\)이므로 합은 \(8\)이다.
riseoj 작성
출처 Original
평가 및 의견
마법 격자의 넓이
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 격자의 넓이