We consider a rectangular grid of size \(n \times m\) with a start cell \((s_x, s_y)\) and an end cell \((e_x, e_y)\). There are \(s\) "bad" cells that act as centers of circles with equal radius \(R\). A cell is blocked if its Euclidean distance to any bad cell is \(\le R\). The goal is to find the smallest non‑negative integer \(R\) such that there exists a 4‑connected path of unbolcked cells from start to end. (If start and end coincide, the answer is simply the distance to the nearest bad cell.)

A binary search on \(R\) is natural. The main difficulty is to decide, for a given \(R\), which cells are blocked. We present two different strategies that achieve a global time complexity of \(O(nm \log (n^2+m^2))\) or better.

---

Method 1: Pre‑compute Minimal Distance to Any Bad Cell

Instead of recomputing coverage for each binary search iteration, we first compute for every grid cell the squared Euclidean distance to the nearest bad cell (call this value \(d[i][j]\)). Then a cell is blocked for a given \(R\) iff \(d[i][j] \le R^2\). The pre‑computation uses an \(O(nm)\) process based on a monotone candidate list.

Define two auxiliary arrays: above[i][j] = the row of the nearest bad cell in column \(j\) that is at or above row \(i\) (or 0 if none), and below[i][j] = the row of the nearest bad cell in column \(j\) that is at or below row \(i\) (or \(n+1\) if none). These are obtained by scanning each column from top to bottom and bottom to top.

We now compute the minimum distance over all four quadrants relative to each cell. For a fixed row \(i\), we consider the candidates given by above[i][j] (i.e., bad cells that are in the same column \(j\) and lie above or on row \(i\)). We process columns left to right and right to left, maintaining a linked list of columns that have a candidate bad cell. The list is kept such that the first element gives the smallest distance to the current column. When a new candidate is added, we compute when it will become worse than the previous candidate and schedule its removal. The key observation: for two consecutive candidates in the list, the left candidate becomes worse as the current column moves right, because the horizontal difference increases while the vertical distance remains fixed. This allows us to pop dominated candidates in amortised constant time.

The same procedure is repeated using below[i][j] and reversing the direction, then the whole process is mirrored for the other two quadrants. Finally, \(d[i][j]\) is the minimum over all directions. The entire pre‑computation runs in \(O(nm)\) time.

After having \(d[i][j]\), we can sort all cells by \(d\) in decreasing order. We then process cells in that order, adding them one by one to the visited set and maintaining connectivity via a union‑find structure. The moment the start and end become connected, the minimum achievable \(R\) is the current cell's distance (rounded appropriately). This eliminates the need for binary search.

#include <bits/stdc++.h>
using namespace std;

int n, m, s, sx, sy, ex, ey;
bool bad[1010][1010];
int up[1010][1010], down[1010][1010];

int sq(int x) { return x * x; }
int dist2(int x1, int y1, int x2, int y2) {
    return sq(x1 - x2) + sq(y1 - y2);
}

// Linked list based monotone candidate management
list<int> cand;
list<int>::iterator ptr[1010];
vector<int> ops[1010];
int mindist[1010][1010];

int removal_time(int diff, int col1, int col2) {
    int inc = 2 * abs(col1 - col2);
    return max(0, (diff + inc - 1) / inc);
}

void process_direction(int (*dir)[1010], int step) {
    for (int r = 1; r <= n; ++r) {
        cand.clear();
        for (int c = 1; c <= m; ++c) {
            ptr[c] = cand.end();
            ops[c].clear();
        }

        int start = (step == 1) ? 1 : m;
        int end   = (step == 1) ? m : 1;
        for (int c = start; (step == 1) ? c <= end : c >= end; c += step) {
            if (dir[r][c]) {  // there is a bad cell at (dir[r][c], c) for this row
                cand.push_back(c);
                ptr[c] = --cand.end();
                if (cand.size() > 1) {
                    int prev = *prev(prev(cand.end()));
                    int cur  = *prev(cand.end());
                    int d = dist2(dir[r][prev], prev, r, c) -
                            dist2(dir[r][cur], cur, r, c);
                    int t = c + step * removal_time(d, prev, cur);
                    if (t >= 1 && t <= m) ops[t].push_back(prev);
                }
            }

            // process scheduled removals for this column
            for (int x : ops[c]) {
                if (cand.empty() || *ptr[x] != x) continue;
                auto it = ptr[x];
                auto nxt = next(it);
                if (nxt == cand.end()) continue;
                if (dist2(dir[r][*it], *it, r, c) >=
                    dist2(dir[r][*nxt], *nxt, r, c)) {
                    // remove left candidate
                    if (it == cand.begin()) {
                        ptr[*it] = cand.end();
                        cand.erase(it);
                    } else {
                        ptr[*it] = cand.end();
                        auto left = prev(it);
                        cand.erase(it);
                        int d = dist2(dir[r][*left], *left, r, c) -
                                dist2(dir[r][*nxt], *nxt, r, c);
                        int t = c + step * removal_time(d, *left, *nxt);
                        if (t >= 1 && t <= m) ops[t].push_back(*left);
                    }
                }
            }

            if (!cand.empty()) {
                int best_col = cand.front();
                int val = dist2(dir[r][best_col], best_col, r, c);
                if (val < mindist[r][c]) mindist[r][c] = val;
            }
        }
    }
}

struct DSU {
    int parent[1010*1010];
    void init() { memset(parent, 0, sizeof(parent)); }
    int find(int x) {
        return parent[x] ? parent[x] = find(parent[x]) : x;
    }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) parent[a] = b;
    }
} dsu;

int id(int r, int c) { return (r-1)*m + c; }

pair<int,int> order[1010*1010];
bool vis[1010][1010];

int main() {
    scanf("%d%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey, &s);
    for (int i = 0; i < s; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        bad[x][y] = true;
    }

    // precompute nearest bad above / below per column
    for (int j = 1; j <= m; ++j) {
        int last = 0;
        for (int i = 1; i <= n; ++i) {
            if (bad[i][j]) last = i;
            up[i][j] = last;
        }
        last = 0;
        for (int i = n; i >= 1; --i) {
            if (bad[i][j]) last = i;
            down[i][j] = last;
        }
    }

    // precompute mindist
    memset(mindist, 0x3f, sizeof(mindist));
    // four quadrant passes
    process_direction(up, -1);   // leftward, using above
    process_direction(down, 1);  // rightward, using below
    process_direction(down, -1); // leftward, using below
    process_direction(up, 1);    // rightward, using above

    if (sx == ex && sy == ey) {
        printf("%d\n", mindist[sx][sy]);
        return 0;
    }

    // sort cells by decreasing mindist
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            order[++cnt] = {i, j};
    sort(order + 1, order + cnt + 1,
         [](const pair<int,int> &a, const pair<int,int> &b) {
             return mindist[a.first][a.second] > mindist[b.first][b.second];
         });

    dsu.init();
    for (int k = 1; k <= cnt; ++k) {
        int x = order[k].first, y = order[k].second;
        vis[x][y] = true;
        if (vis[x+1][y]) dsu.unite(id(x,y), id(x+1,y));
        if (vis[x-1][y]) dsu.unite(id(x,y), id(x-1,y));
        if (vis[x][y+1]) dsu.unite(id(x,y), id(x,y+1));
        if (vis[x][y-1]) dsu.unite(id(x,y), id(x,y-1));
        if (dsu.find(id(sx,sy)) == dsu.find(id(ex,ey))) {
            printf("%d\n", mindist[x][y]);
            return 0;
        }
    }
    puts("0");
    return 0;
}

---

Method 2: Per‑Check Difference Array with Two Candidate Circles

Instead of pre‑computing distances, we can process each binary search check directly in \(O(nm)\) time. The idea is to observe that for a given cell \((x,y)\), only the two nearest bad cells in the same column – one above and one below – are relevant. Any other bad cell in that column will produce a circle that is stritcly contained in the union of the circles from these two closest ones, because they have larger vertical distance and therefore a smaller horizontal radius on row \(x\).

Thus for a fixed radius \(R\), for each column \(j\) we compute the nearest bad row above (or equal) and below (or equal) for every row \(i\). For each cell \((i,j)\) we determine the vertical difference \(dv\) to the nearest bad cell above and below. If \(dv^2 < R^2\) then that bad cell contributes a horizontal interval on row \(i\): [j - floor(sqrt(R^2 - dv^2) - 1e-9), j + floor(sqrt(R^2 - dv^2))]. We apply a difference array on row \(i\) for that interval. Since we only have at most two intervals per cell, the total work per check is \(O(nm)\).

After marking the blocked cells on each row, we perform a BFS or union‑find to test connectivity of the unblocked cells. Union‑find is convenient: we iterate all cells, and for each unblocked cell we union it with its unblocked neighbours (typically only right and down to avoid duplicate unions). Then check if start and end are unblocked and in the same component.

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m, sx, sy, ex, ey, s;
bool bad[N][N];
int up[N][N], down[N][N];
int diff[N][N];  // difference array per row

struct DSU {
    int fa[N*N];
    void init() { memset(fa, 0, sizeof(fa)); }
    int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) fa[a] = b;
    }
} dsu;

int id(int r, int c) { return (r-1)*m + c; }

bool check(int R) {
    memset(diff, 0, sizeof(diff));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int dv = N; // large
            if (up[i][j]) dv = min(dv, i - up[i][j]);
            if (down[i][j]) dv = min(dv, down[i][j] - i);
            if (R*R - 1 < dv*dv) continue; // no contribution
            int half = (int)sqrt(R*R - 1 - dv*dv);
            // half is the horizontal radius (R - 0.5 because of integer distances)
            int left  = max(1, j - half);
            int right = min(m, j + half);
            diff[i][left]  += 1;
            diff[i][right + 1] -= 1;
        }
    }

    // build blocked array
    vector<vector<bool>> blocked(n+2, vector<bool>(m+2, false));
    for (int i = 1; i <= n; ++i) {
        int cur = 0;
        for (int j = 1; j <= m; ++j) {
            cur += diff[i][j];
            if (cur > 0) blocked[i][j] = true;
        }
    }

    if (blocked[sx][sy] || blocked[ex][ey]) return false;

    dsu.init();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (blocked[i][j]) continue;
            if (i < n && !blocked[i+1][j])
                dsu.unite(id(i,j), id(i+1,j));
            if (j < m && !blocked[i][j+1])
                dsu.unite(id(i,j), id(i,j+1));
        }
    }
    return dsu.find(id(sx,sy)) == dsu.find(id(ex,ey));
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey);
    scanf("%d", &s);
    for (int i = 0; i < s; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        bad[x][y] = true;
    }

    // precompute nearest bad above / below per column
    for (int j = 1; j <= m; ++j) {
        int last = 0;
        for (int i = 1; i <= n; ++i) {
            if (bad[i][j]) last = i;
            up[i][j] = last;
        }
        last = n+1;
        for (int i = n; i >= 1; --i) {
            if (bad[i][j]) last = i;
            down[i][j] = last;
        }
    }

    int ans = 0;
    // binary search on R (max distance = 2*n*n)
    for (int bit = 29; bit >= 0; --bit) {
        int nxt = ans + (1 << bit);
        if (nxt <= 2*n*n && check(nxt))
            ans = nxt;
    }
    printf("%d\n", ans);
    return 0;
}