공부정리

2n개의 수 {a1,a2,,,,a2n}이 주어졌을 때 n개의 좌표쌍을 고르고 이 좌표들을 덮을 수 있는 가장 작은 사각형의 넓이를 구하는 문제다.

동일한 위치의 좌표가 여러개일 수 있다.

i번째 수를 x좌표로 골랐다고 생각해 보자. 사각형은 이 점을 반드시 덮어야 한다.

사각형의 왼쪽 아래 점을 (x1,y1) 오른쪽 위 점을 (x2,y2)라고 할 때 x1<=ai<=x2여야 한다. 

결국 n개의 좌표쌍을 골랐을 때 사각형의 윗면은 max_x, 아랫면은 min_x가 되고

왼쪽은 min_y, 오른쪽은 max_y가 되므로 사각형의 넓이는 (max_x - min_x) * (max_y - min_y)가 된다.

선택을 쉽게하기 위해서 일단 정렬을 한다.

이제부터 x좌표를 n개 고를건데 이걸 네가지로 분류해 보자

1. x좌표의 최소값이 a[0], 최대값이 a[i] (i!=2*n-1)일 경우

  최소값과 최대값 사이에서 n개를 고를 수 있어야 하므로 i>=n-1을 만족해야 한다.

  또한 나머지 값들이 y좌표값이 되므로 y의 최소값은 a[j] (j!=0), 최대값은 a[2*n-1]이 되고 j<=n을 만족해야 한다.

  정렬이 되어 있으므로 (a[i] - a[0]) * (a[2*n-1] - a[j])의 최소값은 i==n-1, j==n일때 나온다. O(1)

2. x좌표의 최소값이 a[i] (i!=0), 최대값이 a[2*n-1]일 경우

  여기서 x좌표값이 아니라 y좌표값을 a[i]~a[2*n-1]에서 고른다고 생각하면 1번의 경우와 완전히 일치한다. 따라서 구할 필요가 없다.

3. x좌표의 최소값이 a[i] (i!=0), 최대값이 a[j] (j!=2*n-1)일 경우

  i~j사이에서 n개를 고를 수 있어야 하므로 j-i+1>=n을 만족해야 한다.

  또한 x좌표를 저렇게 골랐으므로 y좌표는 a[0], a[2*n-1]을 무조건 포함한다. 따라서 사각형의 넓이는

  (a[2*n-1] - a[0]) * (a[j] - a[i])가 되고 a[j]-a[i]는 j == n+i-1일 때 최소값이 된다. O(n)

4. x좌표의 최소값이 a[0], 최대값이 a[2*n-1]일 경우

  2번의 경우와 마찬가지로 x를 y로 생각해보면 3번과 동일하다.