광고판 점유 면적
골드 II의견: 0
도심에 \(N\) 개의 축에 평행한 직사각형 광고판이 설치되어 있습니다. 각 광고판은 왼쪽 아래 꼭짓점 \((x_1, y_1)\) 과 오른쪽 위 꼭짓점 \((x_2, y_2)\) 로 주어집니다(\(x_1 < x_2\), \(y_1 < y_2\)).
여러 광고판이 겹칠 수 있습니다. 광고판들이 덮고 있는 영역(합집합)의 총 면적을 구하세요. 겹치는 부분은 한 번만 셉니다.
면적은 항상 정수입니다.
\(1 \le N \le 100{,}000\), 좌표 절댓값 \(\le 10^9\)
첫 줄에 광고판 수 \(N\) 이 주어집니다. (\(1 \le N \le 100{,}000\))
이어 \(N\) 개의 줄에 정수 \(x_1\ y_1\ x_2\ y_2\) 가 주어집니다. (\(-10^9 \le x_1 < x_2 \le 10^9\), \(-10^9 \le y_1 < y_2 \le 10^9\))
모든 광고판이 덮는 영역의 합집합 면적을 출력합니다.
2
0 0 3 3
2 2 5 5
17두 사각형의 넓이 합 9+9=18 에서 겹치는 1×1=1 을 빼면 합집합 넓이는 17 입니다.
2
0 0 2 2
3 3 5 5
8두 사각형이 겹치지 않으므로 4+4 = 8 입니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
광고판 점유 면적
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
광고판 점유 면적