만드는 중입니다

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

지저분한 바탕화면

면접 대비

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

요약
축에 정렬된 직사각형 n개가 주어질 때, 경계를 포함해 다른 직사각형과 겹치는 것의 개수를 센다.
난이도

쉬움10점 중 3점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

많은 회사가 생산성을 높이려고 ‘종이 없는 사무실’로 옮겨가고 있습니다. 하지만 종이를 정리하지 못하던 사람은 종이가 없어도 여전히 정리를 못 합니다! 책상 위에 종이 더미가 흩어져 있는 대신, 화면 위에는 창(window)들이 서로 겹치고 가려집니다. 이런 사람들에게는 화면에서 원하는 창을 찾는 일이 책상에서 원하는 종이를 찾는 일만큼이나 어렵습니다.

이 문제에서는 컴퓨터 바탕화면에 놓인 창 nn개의 위치와 크기가 주어집니다 (1≤n≤501 \le n \le 50). 바탕화면이 얼마나 지저분한지를, 다른 창과 하나라도 겹치는 창의 개수로 평가하려고 합니다. 두 창은 두 창 모두에 포함되는 픽셀이 하나라도 있으면(창의 경계 포함) 서로 겹친다고 봅니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스는 정수 nn이 적힌 줄로 시작하고, 이어서 nn개의 줄에 다음과 같은 형식으로 창이 하나씩 주어집니다.

r c w h

여기서 rr, cc는 창의 왼쪽 위 모서리의 행(row)과 열(column) 좌표이고, ww, hh는 창의 너비(width)와 높이(height)입니다. 즉 이 창은 행 rr부터 r+h−1r+h-1까지, 열 cc부터 c+w−1c+w-1까지의 픽셀을 차지합니다. 바탕화면의 왼쪽 위 모서리는 좌표 (0,0)(0, 0)이고, 화면은 10241024개의 행과 12801280개의 열로 이루어져 있으며, 모든 창은 화면 경계 안에 완전히 들어갑니다. n=0n = 0인 줄이 나오면 입력이 끝납니다.

출력

각 테스트 케이스마다, 다른 창과 하나라도 겹치는 창의 개수를 한 줄에 출력합니다.

예제1

  1. 예제 1

    입력
    3
    0 0 20 20
    20 20 20 20
    40 40 20 20
    5
    0 0 20 20
    18 18 20 20
    40 40 20 20
    5 10 4 2
    100 100 40 40
    0
    
    예상 출력
    0
    3