Problem Statement
x, y축과 평행한 L 자 모양의 직각다각형을 사용하여 , 평면 상에 있는 입력받은 점들을 모두 커버하는 최소 다각형의 넓이를 구하는 프로그램을 작성하시오. 점은 최대 5만개이다.
Analysis
우선 입력받은 좌표를 평행이동하여 모든 점이 1사분면에 오도록 만들 수 있습니다. 그러면 모든 점을 포함하는 최소 크기의 직사각형을 그릴 수가 있지요. L 자 모양의 직각다각형은 이 직사각형에서 오른쪽 위 점을 기준으로 왼쪽아래방향으로 직사각형을 그려서 제외한 다각형으로 볼 수 있지요.
위의 그림과 같은 형태가 될 것입니다. 일단 오른쪽 위 점을 지나고, 다른 한 점을 잡고 사각형을 그렸을 때, 그 구간에 아무런 점이 없게 되는 영역을 그려보면, 계단 모양의 그림이 나오게 됩니다. 우리는 이 계단모양의 사각형 중에서 제일 큰 사각형을 찾아서 빼 주면 되는 거지요.
y 좌표값을 기준으로 decreasing 하도록 정렬을 해 줍니다. (만약 같다면 x 좌표값 기준으로 decreasing) 항상 첫 번째 점은 선택하고 (위의 그림에서 회색) 다음 점들을 차례대로 찾아보면서 현재 점보다 x좌표가 큰 점이 나온다면 선택해 주고 반복합니다. 이러한 과정을 끝까지 진행하면 k개의 회색 점을 구할 수 있지요.
이렇게 찾아진 k 개의 회색 점이 있으면, 인접한 두 개의 회색점을 이용하여 오른쪽 위 점을 하나의 꼭지점으로 하는 사각형들을 구성할 수 있습니다. 이렇게 만들어진 k-1개의 사각형 중 최대 크기( L자 모양의 넓이는 전체사각형 - 오른쪽 위 점을 꼭지점으로 하는 사각형이 되니까요.)를 찾으면 됩니다. 결국 sort만 해결한다면 간단한 greedy 문제였습니다. sort 관련된 문제는 이전 모의고사때도 있었고 찾아보면 많이 나오니까 패스할께요 :D
은근히 함정이 숨어있던 문제였습니다. 입력되는 좌표 범위가 -30000 ~ 30000 이므로 L-Shape 의 크기( 최대크기가 약 30000 * 30000 = 36 억 ) 가 int 범위 (2147483648 = 21 억) 를 넘는 경우가 생기므로 답은 반드시 long long 이나 unsigned int 로 저장해야 합니다. 이 조건 안챙겨줘서 못푼 후배가 있었다는...;
astein
16년 전