파일 업로드

울타리 칠하기

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

몇 차례의 혹독한 겨울을 견뎌낸 후, 범수는 그의 부동산 울타리를 다시 칠하기로 결정했습니다. 그의 부동산은 N개의 울타리로 둘러싸인 구역(1 <= N <= 50,000)으로 구성되어 있으며, 각각은 x축과 y축에 평행한 변을 가진 2차원 평면 상의 직사각형으로 표현됩니다. 구역들은 다른 구역 내에 포함될 수 있지만, 두 울타리가 겹치는 경우는 없으므로, 두 구역이 2차원 평면에서 동일한 영역을 차지한다면, 하나는 다른 하나 안에 포함되어 있어야 합니다.

범수는 다른 구역 안에 들어 있는 구역은 외부에서 볼 수 없다고 생각하여, 다른 구역 안에 포함되지 않은 구역만 다시 칠하려고 합니다. 범수가 칠해야 할 구역의 총 개수를 구해주십시오.

💻 입력
  • 첫 번째 줄 : 구역의 수, N.
  • 두 번째 줄..1+N 번째 줄 : 각 줄은 4개의 공백으로 구분된 정수 x1, y1, x2, y2로 구역을 설명합니다. 여기서 (x1,y1)는 구역의 왼쪽 하단 모서리이며, (x2,y2)는 오른쪽 상단 모서리입니다. 모든 좌표는 0..1,000,000의 범위에 있습니다.
🖨️ 출력
  • 첫 번째 줄 : 다른 구역에 포함되지 않은 구역의 수.

💻 예제 입력 1
3
2 0 8 9
10 2 11 3
4 2 6 5
🖨️ 예제 출력 1
2

출처: USACO 2013 March Contest, Silver Problem 2. Farm Painting