BOJ 1438 - 가장 작은 직사각형
간만에 풀어보는 알고리즘 문제이다.
이므로 항상 고유한 좌표가 이하임을 알 수 있다. 그러면 모든 쌍을 탐색하는데 밖에 안걸린다는 뜻이다.
왜냐면 그리디하게 생각했을 때 가장 크기가 작은 직사각형은 존재하는 좌표 중 두 개를 뽑아서 한 칸씩 늘린 방식(문제에서 직사각형 테두리에 있는 점은 포함 안되는 것으로 본다고 했으므로)으로 표현되기 때문이다.
좌표압축으로 2차원 누적합 배열을 만들어두고 특정 사각형에 있는 점의 개수를 에 쿼리할 수 있다면 시간복잡도 로 문제를 해결할 수 있다.
더 빠르게 구현하는 방법은 투포인터를 이용하는 것이다.
구간을 탐색하며 에 대해 투포인터를 하면 에 문제를 해결할 수 있다.
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;
}
Comments