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

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

직사각형

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

요약
최대 7000개의 축에 평행한 정수 좌표 직사각형이 주어질 때, 겹치는 부분이 양의 길이 선분을 포함하면 같은 블록으로 합쳐지는 연결 요소의 개수를 센다.
난이도

보통10점 중 6점

유형
유니온 파인드, 기하, 정렬, 시뮬레이션
정답자
아직 제출이 없습니다

문제

평면 위에 nn개의 직사각형이 그려져 있습니다. 각 직사각형은 변이 좌표축과 평행하며, 꼭짓점의 좌표는 모두 정수입니다. 블록을 다음과 같이 정의합니다.

  • 직사각형 하나는 그 자체로 하나의 블록입니다.
  • 서로 다른 두 블록이 공통인 선분을 가지면, 두 블록이 합쳐져 하나의 새 블록이 됩니다. 공통인 선분이 없으면 두 블록은 서로 분리되어 있다고 봅니다.

여기서 두 직사각형이 '공통인 선분을 가진다'는 것은, 두 직사각형이 차지하는 영역이 겹치는 부분에 길이가 양수인 선분이 포함된다는 뜻입니다. 구체적으로 두 직사각형이 한 변의 일부를 맞대고 있거나 넓이가 양수인 영역에서 겹치면 같은 블록에 속합니다. 반대로 두 직사각형이 한 점(꼭짓점)에서만 만나거나 아예 만나지 않으면 서로 다른 블록입니다.

아래 첫 번째 그림의 직사각형들은 서로 분리된 두 개의 블록을 이룹니다.

아래 두 번째 그림의 직사각형들은 하나의 블록을 이룹니다.

표준 입력으로 직사각형의 개수와 각 직사각형의 꼭짓점 좌표가 주어질 때, 이 직사각형들이 이루는 분리된 블록의 개수를 구하여 표준 출력에 출력하는 프로그램을 작성하세요.

입력

첫째 줄에 직사각형의 개수 nn이 주어집니다 (1≤n≤70001 \le n \le 7000). 다음 nn개의 줄에는 각 직사각형의 정보가 한 줄에 하나씩 주어집니다. 각 줄에는 네 개의 정수가 주어지며, 순서대로 직사각형의 왼쪽 아래 꼭짓점의 xx좌표와 yy좌표, 오른쪽 위 꼭짓점의 xx좌표와 yy좌표를 나타냅니다. 모든 좌표는 1000010000 이하의 음이 아닌 정수입니다.

출력

첫째 줄에 주어진 직사각형들이 이루는 분리된 블록의 개수를 하나의 정수로 출력합니다.

예제3

  1. 예제 1

    입력
    9
    0 3 2 6
    4 5 5 7
    4 2 6 4
    2 0 3 2
    5 3 6 4
    3 2 5 3
    1 4 4 7
    0 0 1 4
    0 0 4 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    1
    0 0 5 5
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2
    0 0 2 2
    2 0 4 2
    
    예상 출력
    1