Editorial for VO 16 Bài 1 - Di chuyển hình chữ nhật


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Cần cực tiểu hóa khoảng cách di chuyển max của các hình nhữ nhật. Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân ~V~, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng ~V~. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá ~V~ thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện ~N~ hình chữ nhật có phần giao chung hay không là ~max(X1) < min(X2)~ và ~max(Y1) < min(Y2)~.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const long long INF = (long long)1e12;

long long x[N], y[N], u[N], v[N];
int n;

bool check(long long length) {
    long long L = -INF, U = INF, R = INF, D = -INF;
    for (int i = 1; i <= n; ++i) {
        L = max(L, y[i] - length); R = min(R, v[i] + length);
        D = max(D, x[i] - length); U = min(U, u[i] + length);
    }
    return L < R && D < U;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i] >> u[i] >> v[i];
    long long l = 0, r = INF, ans = -1;
    while (l <= r) {
        long long mid = l + r >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.