思路与算法

二分正方形边长L。一个建筑占用格子[x1,x2]×[y1,y2]时，禁止的左下角为[x1-L+1,x2]×[y1-L+1,y2]，裁到可行左下角域。扫x，对y禁区做区间加，若某段候选x处覆盖最小值为0则存在空方块。起始事件按原x1、结束事件按x2预排序，L改变后仍可线性合并；y坐标用有界整数标记压缩。

正确性说明

方块与建筑有公共格子恰等价其左下角落入扩张禁区，故全体禁区并集之外的点与空方块一一对应。扫线在相邻事件间覆盖不变，区间最小值准确判断是否有未覆盖y。能放L方块就能在其内部放更小方块，判定单调，答案二分正确。

复杂度

设p建筑数，坐标宽m≤1e6。预排序O(plogp)，每次判定初始化及压缩O(m+p)，事件更新O(plog(p+m))，总O(plogp+log(min(n,m))·(m+p+plog(p+m)))时间，O(m+p)空间。

易错点

输入坐标是被建筑占用的格子端点，须包含x2,y2，不是连续几何开边界。重叠建筑用覆盖次数累计。事件同x时全处理后判定，退出事件位于右端加1。满占时答案0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct B {
    int x, y, X, Y;
};
struct E {
    int x, l, r, v;
    bool operator<(const E &e) const {
        return x < e.x;
    }
};
struct Seg {
    int n;
    vector<int> mn, lz;
    Seg(int n) : n(n), mn(4 * n), lz(4 * n) {
    }
    void add(int ql, int qr, int v, int u, int l, int r) {
        if (ql <= l && r <= qr) {
            mn[u] += v;
            lz[u] += v;
            return;
        }
        int mid = (l + r) / 2;
        if (ql <= mid)
            add(ql, qr, v, u * 2, l, mid);
        if (qr > mid)
            add(ql, qr, v, u * 2 + 1, mid + 1, r);
        mn[u] = lz[u] + min(mn[u * 2], mn[u * 2 + 1]);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, p;
    while (cin >> n >> m >> p) {
        vector<B> a(p);
        for (auto &b : a)
            cin >> b.x >> b.y >> b.X >> b.Y;
        vector<int> xs(p), xe(p);
        iota(xs.begin(), xs.end(), 0);
        iota(xe.begin(), xe.end(), 0);
        sort(xs.begin(), xs.end(), [&](int i, int j) {
            return a[i].x < a[j].x;
        });
        sort(xe.begin(), xe.end(), [&](int i, int j) {
            return a[i].X < a[j].X;
        });
        auto feasible = [&](int side) {
            int N = n - side + 1, M = m - side + 1;
            vector<int> rank(M + 2, -1);
            rank[1] = rank[M + 1] = 0;
            for (auto b : a) {
                rank[max(1, b.y - side + 1)] = 0;
                rank[min(M, b.Y) + 1] = 0;
            }
            int count = 0;
            for (int y = 1; y <= M + 1; y++)
                if (rank[y] == 0)
                    rank[y] = count++;
            Seg st(count - 1);
            int ia = 0, ib = 0, x = 1;
            while (x <= N) {
                while (ia < p && max(1, a[xs[ia]].x - side + 1) <= x) {
                    auto b = a[xs[ia++]];
                    int l = rank[max(1, b.y - side + 1)], r = rank[min(M, b.Y) + 1] - 1;
                    st.add(l, r, 1, 1, 0, st.n - 1);
                }
                while (ib < p && min(N, a[xe[ib]].X) + 1 <= x) {
                    auto b = a[xe[ib++]];
                    int l = rank[max(1, b.y - side + 1)], r = rank[min(M, b.Y) + 1] - 1;
                    st.add(l, r, -1, 1, 0, st.n - 1);
                }
                if (!st.mn[1])
                    return true;
                int ns = ia < p ? max(1, a[xs[ia]].x - side + 1) : N + 1,
                    ne = ib < p ? min(N, a[xe[ib]].X) + 1 : N + 1;
                x = min(ns, ne);
            }
            return false;
        };
        int lo = 0, hi = min(n, m);
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (feasible(mid))
                lo = mid;
            else
                hi = mid - 1;
        }
        cout << lo << '\n';
    }
}