격자 패널을 생산하는 공장이 있다. 생산 과정 중에 가끔씩 손상된 패널이 나타나는데 이는 패널의 격자점에 구멍이 생기는 것이다. 공장에서는 손상된 패널들을 모두 모아서 재처리를 하게 된다. 재처리 과정에서 패널에 구멍이 생긴 부분을 도려낸다. 이 때 항상 패널의 격자선을 따라서 절단한다. 도려내는 부분은 다음을 만족하는 하나의 연결된 조각이어야 한다.

(i) 각 구멍에 인접한 격자셀들을 모두 포함한다. (ii) 절단의 기준 스트립(strip)으로 선택된 패널의 한 행 또는 한 열에 위치한 모든 셀들을 포함한다. (iii) 도려낼 조각은 직교볼록 다각형이다. (iv) 위의 조건을 만족하는 직교볼록 다각형 중에서 최소 면적을 가진다.

직교 다각형은 경계선이 수평 선분과 수직 선분만으로 구성된 다각형이다 직교볼록 다각형은 그 내부와 어떤 수직선 또는 수평선과의 교차 영역이 공백이거나 한 개의 선분만으로 구성되는 직교 다각형이다.

예를 들어, 그림 1 (a)와 같이 6개의 구멍을 가진 패널을 보자 절단의 기준 스트립으로 밑에서 네 번째 행을 선택한다면, 도려낼 조각은 그림 1 (b)와 같이 29개의 셀을 포함하는 영역이다. 만일 왼쪽에서 네 번째 열이 기준 스트립으로 선택되면, 그림 1 (c)와 같이 27개의 셀을 포함하는 영역을 도려낸다

문제는 패널의 크기와 구멍의 위치 정보가 주어질 때, 위의 조건을 만족하는 최소 크기의 직교볼록 다각형의 면적을 구하는 프로그램을 작성하는 것이다. 한 개 격자셀의 면적이 1이므로, 그림 1 (c)의 직교볼록 다각형의 면적은 27이다.

#2560 upload 13 done 2 how_to_reg 1

패널 timer 1s memory - MB

#2560

패널 1s - MB