二分 #单调队列 #bfs #POI #Year2006

具有单调性，二分

从上往下考虑每一行，对于每一列维护一个单调队列，考虑维护一个覆盖的区间，表示这一列的最近的圆的位置，然后就可以计算它的覆盖区间

用差分计算每个位置是否被覆盖，处理当前长度下每个点是否被覆盖

然后 \(bfs\) 即可

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e3 + 10;

int n, m;
int sx, sy, tx, ty, tot;
pii a[1000005];
int st[N][N], hd[N], tl[N];
bool vis[N][N];
int dif[N];
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {1, -1, 0, 0};

bool check(int x)
{
	mms(st, 0);
	mms(vis, 0);
	mms(hd, 0);
	mms(tl, 0);
	mms(dif, 0);
	int dis = sqrt(x);
	int l = 1, r = 1;
	rep(i, 1, n)
	{
		mms(dif, 0);
		while (i + dis >= a[r].first && r <= tot)
		{
			st[a[r].second][tl[a[r].second]++] = a[r].first;
			r++;
		}
		while (i - dis > a[l].first && l <= tot)
		{
			if (st[a[l].second][hd[a[l].second]] == a[l].first)
				hd[a[l].second]++;
			l++;
		}
		rep(j, 1, m)
		{
			while (st[j][hd[j] + 1] && abs(st[j][hd[j]] - i) >= abs(st[j][hd[j] + 1] - i))
				hd[j]++;
			int cur = st[j][hd[j]];
			// debug(cur);
			if (!cur)
				continue;
			int rd = sqrt(x - (cur - i) * (cur - i));
			dif[max(1, j - rd)]++;
			dif[min(m, j + rd) + 1]--;
		}
		rep(j, 1, m)
		{
			dif[j] += dif[j - 1];
			vis[i][j] = (dif[j] > 0);
		}
	}
	// rep(i, 1, n)
	// {
	// 	rep(j, 1, m) cerr << vis[i][j] << ' ';
	// 	cerr << endl;
	// }
	// cerr << endl;
	// debug(vis);
	if (vis[sx][sy])
		return false;
	queue<pii> q;
	q.push({sx, sy});
	// vis[sx][sy] = true;
	while (!q.empty())
	{
		auto [x, y] = q.front();
		q.pop();
		if (x == tx && y == ty)
			return true;
		rep(i, 0, 3)
		{
			int xx = x + dx[i], yy = y + dy[i];
			if (xx < 1 || yy < 1 || xx > n || yy > m)
				continue;
			if (vis[xx][yy])
				continue;
			vis[xx][yy] = true;
			q.push({xx, yy});
		}
	}
	return false;
}

void solve()
{
	cin >> n >> m >> sx >> sy >> tx >> ty;
	cin >> tot;
	rep(i, 1, tot) cin >> a[i].first >> a[i].second;
	sort(a + 1, a + tot + 1);
	int l = -1, r = 2e6;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid))
			l = mid;
		else
			r = mid - 1;
	}
	cout << l + 1 << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}