Description：

给定一个网格图，其中有一些坏点，要求使起点到终点的路径上的所有点到离该点最近的坏点的最小欧几里得距离的平方最大，求这个最大值。

$1\leqslant n,m \leqslant1000$

Solution：

首先假设已经求出了每个点到坏点的欧几里得距离的平方的最小值，那么我们可以二分距离，把所有距离小于二分的值的位置都删掉，然后判一下起点和终点是否连通就行了。

问题是如何快速求出距离，可以先预处理出同一列上距离每个点最近的坏点，这个可以每一列正反扫两遍求出，然后枚举每一行，对于点 $(x',y')$ ， $(x_1,y_1)$ 优于 $(x_2,y_2)$ 当 $(x_1-x')^2+(y_1-y')^2\leqslant(x_2-x')^2+(y_2-y')^2$ ，化个式子就是 $\frac{x_1^2-x_2^2+y_1^2-y_2^2-2x'(x_1-x_2)}{2(y_1-y_2)}\leqslant y'$ ，设 $calc(p_A,p_B)$ 为不等式左边的部分，也就是说每一行如果 $p_A$ 优于 $p_B$ ，那么之后永远更优，也就是说每个位置合法的都是一段区间，且每个位置离他最近的坏点的位置也是单调的，那么我们就可以维护一个单调队列，队列中的数满足 $calc(q[i],q[i+1])<calc(q[i+1],q[i+2])$ ，也就是说记下了每个可能更新的位置，这样最后扫一遍就能得到没个更新它的位置。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,s;

#define MAXN 1010

int sx,sy,tx,ty;

int p[MAXN][MAXN];

int f[MAXN][MAXN],d[MAXN][MAXN];

typedef long long ll;

ll dis[MAXN][MAXN];

#define INF 0x3f3f3f3f

struct point{int x,y;point(int x_ = 0,int y_ = 0){x = x_;y = y_;}};

point q[MAXN];

int head,tail;

double calc(point a,point b,int x)

{

	return (a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y - 2 * x * (a.x - b.x)) / (a.y - b.y);

}

ll dist(point a,point b)

{

	return (ll)(a.x - b.x) * (a.x - b.x) + (ll)(a.y - b.y) * (a.y - b.y);

}

int fa[MAXN * MAXN];

int to(int i,int j){return (i - 1) * m + j;}

int find(int x){return (x == fa[x] ? x : fa[x] = find(fa[x]));}

int mx[4] = {0,0,1,-1},my[4] = {1,-1,0,0};

bool check(int w)

{

	if(dis[sx][sy] < w || dis[tx][ty] < w)return false;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			fa[to(i,j)] = to(i,j);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(dis[i][j] < w)continue;

			for(int k = 0;k < 4;++k)

			{

				if(1 <= i + mx[k] && i + mx[k] <= n && 1 <= j + my[k] && j + my[k] <= m && dis[i + mx[k]][j + my[k]] >= w)

				{

					fa[find(to(i,j))] = find(to(i + mx[k],j + my[k]));

				}

			}

		}

	}

	return find(to(sx,sy)) == find(to(tx,ty));

}

int main()

{

	scanf("%d%d",&n,&m);

	scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

	scanf("%d",&s);

	int x,y;

	for(int i = 1;i <= s;++i)

	{

		scanf("%d%d",&x,&y);

		p[x][y] = 1;

	}

	memset(d,0x3f,sizeof(d));

	memset(f,0,sizeof(f));

	for(int j = 1;j <= m;++j)

	{

		int cur = 0;

		for(int i = 1;i <= n;++i)

		{

			if(p[i][j])cur = i;

			if(cur != 0 && d[i][j] > (i - cur) * (i - cur))

			{

				f[i][j] = cur;

				d[i][j] = (i - cur) * (i - cur);

			}

		}

		cur = 0;

		for(int i = n;i >= 1;--i)

		{

			if(p[i][j])cur = i;

			if(cur != 0 && d[i][j] > (i - cur) * (i - cur))

			{

				f[i][j] = cur;

				d[i][j] = (i - cur) * (i - cur);

			}

		}

	}

	for(int i = 1;i <= n;++i)

	{

		head = 1;tail = 0;

		q[++tail] = (point){i,-INF};

		for(int j = 1;j <= m;++j)

		{

			if(d[i][j] == INF)continue;

			while(head < tail && calc((point){f[i][j],j},q[tail],i) < calc(q[tail],q[tail - 1],i))--tail;

			q[++tail] = (point){f[i][j],j};

		}

		for(int j = 1;j <= m;++j)

		{

			while(head < tail && dist(q[head],(point){i,j}) > dist(q[head + 1],(point){i,j}))++head;

			dis[i][j] = dist(q[head],(point){i,j});

		}

	}

	int l = 0,r = n * m,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(check(mid))l = mid;

		else r = mid - 1;

	}

	cout << l << endl;

	return 0;

}