지저분한 바탕화면
면접 대비시간 제한7초메모리 제한128 MB
축에 정렬된 직사각형 n개가 주어질 때, 경계를 포함해 다른 직사각형과 겹치는 것의 개수를 센다.
문제
많은 회사가 생산성을 높이려고 ‘종이 없는 사무실’로 옮겨가고 있습니다. 하지만 종이를 정리하지 못하던 사람은 종이가 없어도 여전히 정리를 못 합니다! 책상 위에 종이 더미가 흩어져 있는 대신, 화면 위에는 창(window)들이 서로 겹치고 가려집니다. 이런 사람들에게는 화면에서 원하는 창을 찾는 일이 책상에서 원하는 종이를 찾는 일만큼이나 어렵습니다.
이 문제에서는 컴퓨터 바탕화면에 놓인 창 개의 위치와 크기가 주어집니다 (). 바탕화면이 얼마나 지저분한지를, 다른 창과 하나라도 겹치는 창의 개수로 평가하려고 합니다. 두 창은 두 창 모두에 포함되는 픽셀이 하나라도 있으면(창의 경계 포함) 서로 겹친다고 봅니다.
입력
입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스는 정수 이 적힌 줄로 시작하고, 이어서 개의 줄에 다음과 같은 형식으로 창이 하나씩 주어집니다.
r c w h
여기서 , 는 창의 왼쪽 위 모서리의 행(row)과 열(column) 좌표이고, , 는 창의 너비(width)와 높이(height)입니다. 즉 이 창은 행 부터 까지, 열 부터 까지의 픽셀을 차지합니다. 바탕화면의 왼쪽 위 모서리는 좌표 이고, 화면은 개의 행과 개의 열로 이루어져 있으며, 모든 창은 화면 경계 안에 완전히 들어갑니다. 인 줄이 나오면 입력이 끝납니다.
출력
각 테스트 케이스마다, 다른 창과 하나라도 겹치는 창의 개수를 한 줄에 출력합니다.