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;
}