BOJ 1438 - 가장 작은 직사각형

BOJ 1438 - 가장 작은 직사각형

간만에 풀어보는 알고리즘 문제이다.

$N \le 100$이므로 항상 고유한 $x,~y$ 좌표가 $100$이하임을 알 수 있다. 그러면 모든 $(x,~y)$쌍을 탐색하는데 $O(N^4)$ 밖에 안걸린다는 뜻이다.

왜냐면 그리디하게 생각했을 때 가장 크기가 작은 직사각형은 존재하는 $(x, ~y)$좌표 중 두 개를 뽑아서 한 칸씩 늘린 방식(문제에서 직사각형 테두리에 있는 점은 포함 안되는 것으로 본다고 했으므로)으로 표현되기 때문이다.

좌표압축으로 2차원 누적합 배열을 만들어두고 특정 사각형에 있는 점의 개수를 $O(1)$에 쿼리할 수 있다면 시간복잡도 $O(N^4)$로 문제를 해결할 수 있다.

더 빠르게 구현하는 방법은 투포인터를 이용하는 것이다.

$[x_1,~x_2]$ 구간을 탐색하며 $y$에 대해 투포인터를 하면 $O(N^3)$에 문제를 해결할 수 있다.

void solve() {
   int n;
   cin >> n;
   vector<pi> a(n);
   vi xpos, ypos;
   for (auto &[y, x]: a) {
      cin >> y >> x;
      xpos.pb(x), ypos.pb(y);
   }
   uniq(xpos);
   uniq(ypos);
   for (auto &[y, x]: a) {
      y = lbi(ypos, y);
      x = lbi(xpos, x);
   }
   debug(a);
   int X = sz(xpos), Y = sz(ypos);
   vvi psum(Y + 1, vi(X + 1)), b(Y + 1, vi(X + 1));
   for (auto &[y, x]: a) {
      assert(!b[y][x]);
      b[y][x] = 1;
   }
   for (int x = 0; x < X; x++) {
      for (int y = 0; y < Y; y++) {
         psum[y + 1][x + 1] =
            psum[y + 1][x] + psum[y][x + 1] - psum[y][x] + b[y][x];
      }
   }
   function<int(int, int, int, int)>
      qry = [&](int y1, int x1, int y2, int x2) -> int {
      return psum[y2 + 1][x2 + 1] - psum[y2 + 1][x1] - psum[y1][x2 + 1]
         + psum[y1][x1];
   };

   int ans = 1e9;
   for (int y1 = 0; y1 < Y; y1++) {
      for (int x1 = 0; x1 < X; x1++) {
         for (int y2 = y1; y2 < Y; y2++) {
            for (int x2 = x1; x2 < X; x2++) {
               int sum = qry(y1, x1, y2, x2);
               if (sum >= n / 2) {
                  int w = xpos[x2] - xpos[x1] + 2;
                  int h = ypos[y2] - ypos[y1] + 2;
                  mina(ans, w * h);
               }
            }
         }
      }
   }
   cout << ans;
}