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

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

구멍 절단기

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

요약
종이 안쪽을 지나는 축에 평행한 절단선들이 만드는 구멍의 개수를 센다.
난이도

보통10점 중 7점

유형
기하, 유니온 파인드, 조합론
정답자
아직 제출이 없습니다

문제

본사의 조수들은 커다란 종이에서 다양한 모양을 잘라내야 할 때가 많다. 예를 들어 여러 크기의 포스터를 나눠 주는 경우가 그렇다. 이들은 이전의 어떤 기계보다도 훨씬 자유롭게 종이를 자를 수 있는 새 절단기를 들였고, 복잡하게 이어지는 절단이 이루어졌을 때 종이에 정확히 어떤 일이 생기는지 계산하는 프로그램을 원한다. 특히 절단으로 인해 종이에 생기는 구멍(hole)의 개수를 알고자 한다. 아래 그림은 절단 후 나타날 수 있는 몇 가지 상황의 예시이다.

구멍 2개구멍 2개구멍 1개구멍 1개

입력

입력은 여러 개의 절단 작업(operation) 설명으로 이루어진다. 각 설명의 첫 줄에는 그 작업에서 이루어지는 절단의 개수 NN이 주어지며, 1≤N≤1001 \le N \le 100이다. 이어지는 NN개의 줄에는 실제 절단이 하나씩 주어진다. 각 절단은 공백으로 구분된 네 정수 X1,Y1,X2,Y2X_1, Y_1, X_2, Y_2로 주어지고, −105<X1,Y1,X2,Y2<105-10^5 < X_1, Y_1, X_2, Y_2 < 10^5이다. (X1,Y1)(X_1, Y_1)은 절단선의 시작점, (X2,Y2)(X_2, Y_2)는 끝점의 좌표이다.

모든 점은 항상 종이 내부에 있으며 경계에는 놓이지 않는다고 가정한다. 각 절단은 테이블의 xx축 또는 yy축에 평행하다. 입력은 N=0N = 0인 절단 작업 설명, 즉 정수 00 하나만 있는 줄로 끝난다.

출력

각 절단 작업마다, 모든 절단을 마친 뒤 종이에 생긴 서로 다른 구멍의 개수를 HH라 할 때 There are H holes. 형식의 문장 한 줄을 출력한다. 어떤 구멍이든 그 최소 넓이는 1 제곱 단위임에 유의하라.

예제4

  1. 예제 1

    입력
    6
    1 0 1 1
    2 0 2 2
    3 1 3 2
    1 0 2 0
    1 1 3 1
    2 2 3 2
    2
    0 1 2 1
    1 2 1 0
    0
    
    예상 출력
    There are 2 holes.
    There are 0 holes.
    
  2. 예제 2

    입력
    4
    0 0 1 0
    1 0 1 1
    1 1 0 1
    0 1 0 0
    0
    
    예상 출력
    There are 1 holes.
    
  3. 예제 3

    입력
    1
    0 0 0 5
    0
    
    예상 출력
    There are 0 holes.
    
  4. 예제 4

    입력
    8
    0 0 4 0
    4 0 4 4
    4 4 0 4
    0 4 0 0
    1 1 3 1
    3 1 3 3
    3 3 1 3
    1 3 1 1
    0
    
    예상 출력
    There are 2 holes.