Hướng dẫn giải của Hình chữ nhật (Đề HSG KonTum 2021)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần tìm hình chữ nhật có cạnh song song với trục tọa độ, đỉnh có tọa độ nguyên, sao cho mọi điểm nằm hoàn toàn bên trong (không nằm trên cạnh). Vì các điểm phải nằm trong, cạnh trái phải nhỏ hơn minx ít nhất 1, cạnh phải lớn hơn maxx ít nhất 1, tương tự với đáy và đỉnh. Diện tích nhỏ nhất đạt được khi các cạnh sát ngoài nhất có thể, tức L = minx - 1, R = maxx + 1, D = miny - 1, U = maxy + 1.
Kiểm tra với ví dụ: minx = -1, maxx = 2, miny = -1, maxy = 1, nên chiều rộng (2 - (-1)) + 2 = 5, chiều cao (1 - (-1)) + 2 = 4, diện tích 20, khớp với đề.
Sub 1: Vét cạn — ~O(n^3)~
Thử mọi cặp điểm i, j để lấy L = x_i - 1 và R = x_j + 1. Với mỗi cặp, kiểm tra mọi điểm có nằm strict trong (L, R) theo chiều ngang không, và tính min/max y để suy ra chiều cao. Lấy diện tích nhỏ nhất trong các cặp hợp lệ. Cách này đúng nhưng chậm khi n = 10^5.
Kết quả chấm: đạt 18/25 test (7 test còn lại quá giờ, không sai).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("HCN.INP", "r")) { freopen("HCN.INP", "r", stdin); freopen("HCN.OUT", "w", stdout); }
int n;
cin >> n;
vector<long long> x(n), y(n);
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
// Cac canh phai nam ngoai diem: canh trai L = x_i - 1, canh phai R = x_j + 1 (thu moi cap i, j).
// Chieu cao: day = min(y) - 1, dinh = max(y) + 1 (tinh bang vong lap cho moi cap).
long long best = LLONG_MAX;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
long long L = x[i] - 1, R = x[j] + 1;
bool ok = true;
long long lo = LLONG_MAX, hi = LLONG_MIN;
// Kiem tra moi diem nam trong (L, R) theo chieu ngang va tim min/max tung chieu
for (int k = 0; k < n; k++) {
if (!(L < x[k] && x[k] < R)) { ok = false; break; }
lo = min(lo, y[k]);
hi = max(hi, y[k]);
}
if (!ok) continue;
long long area = (R - L) * (hi - lo + 2);
best = min(best, area);
}
cout << best << "\n";
return 0;
}
Sub 2: Bounding box — ~O(n)~
Chỉ cần tìm minx, maxx, miny, maxy trong một lần đọc, rồi cộng thêm 2 vào chiều rộng và chiều cao (mỗi phía thêm 1 để điểm nằm trong hẳn). Diện tích là (maxx - minx + 2) * (maxy - miny + 2). Dùng long long vì tọa độ và tích có thể lớn.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("HCN.INP", "r")) { freopen("HCN.INP", "r", stdin); freopen("HCN.OUT", "w", stdout); }
int n;
cin >> n;
long long minx = LLONG_MAX, maxx = LLONG_MIN, miny = LLONG_MAX, maxy = LLONG_MIN;
for (int i = 0; i < n; i++) {
long long x, y;
cin >> x >> y;
minx = min(minx, x); maxx = max(maxx, x);
miny = min(miny, y); maxy = max(maxy, y);
}
// Hinh chu nhat bao quanh nho nhat: canh trai minx-1, phai maxx+1, day miny-1, dinh maxy+1
// (diem phai nam hoan toan ben trong nen moi chieu cong them 2)
long long w = (maxx - minx) + 2;
long long h = (maxy - miny) + 2;
cout << w * h << "\n";
return 0;
}
Bình luận