임의의 점에 대해 해당 점을 포함하는 마름모가 반드시 포함하는 x축 위의 구간을 구할 수 있습니다.
예를 들어 (5, 3) 위치에 점이 있을 경우, 이 점을 포함하는 마름모는 [2, 8] 구간을 항상 덮게 됩니다. 편의상 (5, 3) 점의 xs = 2, xe = 8 이라고 합시다.
또한 임의의 점의 집합이 있을 때, 이 점들을 모두 포함하는 마름모는 [min(xs), max(xe)] 구간을 포함해야 합니다.

이를 이용하면 점들을 xe 기준으로 정렬한 뒤 O(N^2) DP를 구상할 수 있습니다.

대회 참가자가 아니었으므로 이 풀이로 AC를 받을 수 있었을지는 모르겠네요. 더 좋은 풀이가 있는 분은 알려 주세요.

감사합니다
접근조차 못하고 있었는데
많은 도움이 됬습니다
저 방법으로 도전해봐야겠네요
다시 한번 감사합니다

프로필 댓글 확인이 늦었네요.

점들을 xe 기준으로 정렬하고, 다음의 DP를 정의합니다. dp[i] : i번째 점까지 모두 덮도록 마름모를 배치했을 때 넓이의 최솟값

이 때 마지막(가장 오른쪽) 마름모가 j번째부터 i번째 점까지 덮는다고 생각하면, dp[i] = min( dp[j - 1] + (j번째부터 i번째 점까지 덮는 마름모의 최소 넓이) ) for 1 <= j <= i 와 같은 식을 세울 수 있습니다.
위에서 말했듯 어떤 점들을 덮는 마름모의 최소 지름은 max(xe) - min(xs)인데, xe를 기준으로 정렬했으므로 max(xe)는 i번째 점의 xe로 고정됩니다.
따라서 j를 i부터 감소시키며 min(xs)만 갱신해 나가면 j번째부터 i번째 점까지 덮는 마름모의 최소 넓이를 구할 수 있고, 문제를 O(N^2) 에 해결할 수 있습니다.

와.... 저런 방법으로도 모든 경우의 수가 다 체크 되는군요.

제 소스보다 약 4배정도 빠른 속도로 결과가 나오네요. 메모리 부분도 엄청난 차이가 나네요.

많은 공부가 되었습니다. 감사합니다.