만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

환상적인 프라노

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

요약
축에 평행한 직사각형 최대 1000개의 테두리를 원점에서 출발하는 거북이로 그릴 때, 펜을 들어 올리는 최소 횟수를 구합니다.
난이도

보통10점 중 7점

유형
그래프, 유니온 파인드
정답자
아직 제출이 없습니다

그리기

프라노는 여러 해 동안 Logo 대회에서 뛰어난 문제를 만들어 왔습니다. 이런 작업을 오래 하면 심신 건강에 해로울 수 있어서, 프라노는 불필요하게 펜을 들었다 내리는 행위로부터 거북이를 지키는 최초의 투사가 되었습니다. 프라노를 기리며, 이 문제는 Logo 거북이들이 매일 겪는 어려움에 대한 인식을 높이는 것을 목표로 합니다.

Logo의 전형적인 과제는 화면에 직사각형을 그리는 것입니다. 그림은 거북이를 움직여서 그립니다. 거북이는 매 순간 위치와 바라보는 방향을 가지며, 이빨에 펜을 물고 있습니다. 펜은 내려가 있거나 올라가 있을 수 있습니다. 펜이 내려가 있으면 거북이를 움직일 때 화면에 자취가 남습니다.

모든 프로그램은 거북이가 (0,0)(0, 0)에 있고, y축의 양의 방향을 바라보며, 펜이 내려간 상태에서 시작합니다. 거북이는 다음 명령어로만 조종합니다. FD x는 바라보는 방향으로 xx 픽셀 이동시킵니다. LT x는 왼쪽으로 xx도 회전시킵니다. RT x는 오른쪽으로 xx도 회전시킵니다. PU는 펜을 들어 올립니다. PD는 펜을 내립니다.

좌표축과 평행한 변을 가진 직사각형들의 집합이 주어지며, 이 직사각형들을 화면에 그려야 합니다. 거북이는 펜을 내린 상태로 같은 화면 선분을 여러 번 지나갈 수 있습니다. 다만 주어진 직사각형 외에는 아무것도 그릴 수 없습니다.

주어진 직사각형 집합을 그리기 위해 펜을 최소 몇 번 들어야 하는지 구하는 프로그램을 작성하십시오.

입력

첫 줄에 자연수 nn (1≤n≤10001 \le n \le 1000)이 주어집니다. 이는 그려야 할 직사각형의 개수입니다.

이어지는 nn개의 줄에는 각각 정수 네 개 x1x_1, y1y_1, x2x_2, y2y_2 (−500≤x1<x2≤500-500 \le x_1 < x_2 \le 500, −500≤y1<y2≤500-500 \le y_1 < y_2 \le 500)가 주어집니다. 점 (x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)는 직사각형의 대각선 방향 꼭짓점입니다.

출력

주어진 직사각형 집합을 그리기 위해 펜을 최소 몇 번 들어야 하는지 한 줄에 출력합니다.

예제3

  1. 예제 1

    입력
    1
    0 0 10 10
    
    예상 출력
    0
    
  2. 예제 2

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

    입력
    5
    1 1 4 4
    3 3 6 6
    4 4 5 5
    5 0 8 3
    6 1 7 2
    
    예상 출력
    2