题意:
给定1个网格图，其中有1些坏点，要求使出发点到终点的路径上的所有点到离该点最近的坏点的最小距离距离最大，求这个最大值。
解析:
读完题明显分为两部份:
第1部份:预处理所有点到他最近的坏点的距离。
第2部份:2分最大距离bfs判定。
第2部份不用说吧？
主要就是卡在第1部份。
我们斟酌依照每列来计算每一个点的dis距离(即到他最近的坏点的距离)
明显可以发现，对该列来讲，每行都可能有1个到该列最近的点，并且我们发现，如果某1行有两个坏点的话，假定分别为A，B，并且A到该列的距离最近，那末B明显不会对这1列的dis有任何影响。
所以我们明显可以在求之前预处理1下每行的如果存在坏点的那个最近的坏点的坐标。
接下来，我们讨论坏点k,l，设我们要更新的点是(x,y)
如果k优于l，那末我们无妨列1下式子。
(Xk?x)2+(Yk?y)2<=(Xl?x)2+(Yl?y)2
即
X2k?X2l+2?x?Xl?2?x?XkYk?Yl+Yk+Yl<=2y
所以我们只需要按处理出来的坏点顺序保护1个
X2k?X2l+2?x?Xl?2?x?XkYk?Yl+Yk+Yl递增便可。
更新的时候每次在其中2分查找最后1个<=2y的。
复杂度O(n*m*logn)
代码:
using namespace std; int n,m; int num; int calc[N][N]; int xx[]={0,1,-1,0,0}; int yy[]={0,0,0,-1,1};
struct node
{ int x,y;
node(){}
node(int _x,int _y):x(_x),y(_y){}
friend istream& operator >> (istream &_,node &a)
{scanf("%d%d",&a.x,&a.y);calc[a.y][++calc[a.y][0]]=a.x;return _;}
friend bool operator == (node a,node b)
{return a.x==b.x&&a.y==b.y;}
node operator - (const node &a)
{return node(x-a.x,y-a.y);} int operator * (const node &a)
{return x*a.x+y*a.y;}
}pt[N*N],st,ed; int dis[N][N]; int f[N][N];
node q[N];
node newq[N];
void init()
{ for(int i=1;i<=m;i++) sort(calc[i]+1,calc[i]+calc[i][0]+1);
} int get_dis(node a,node b)
{ return (a-b)*(a-b);
}
double q_calc(node a,node b,int tmpx)
{ return (double)(a.x*a.x-b.x*b.x+2*tmpx*b.x-2*tmpx*a.x)/(a.y-b.y)+a.y+b.y;
}
void get_min_dis()
{
memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=num;i++) dis[pt[i].x][pt[i].y]=0; for(int i=1;i<=n;i++) { int l=1,r=0; for(int j=1;j<=m;j++)
{ int ll=1,rr=calc[j][0],ans=ll; while(ll<=rr) { int mid=(ll+rr)>>1; if(calc[j][mid]<=i)ans=mid,ll=mid+1; else rr=mid-1;
} if(ans+1<=calc[j][0]&&abs(calc[j][ans+1]-i)<abs(calc[j][ans]-i))
ans++; if(ans<=calc[j][0])
{
node tmp;
tmp.x=calc[j][ans],tmp.y=j; q[++r]=tmp;
}
} if(r==1)
{ for(int j=1;j<=m;j++)
dis[i][j]=get_dis(node(i,j),q[r]); continue;
} int tmpr=r;
l=1,r=0; for(int j=1;j<=tmpr;j++) { while(lq[j],newq[r],i)<=q_calc(newq[r],newq[r⑴],i))r--; if(l>=r||q_calc(q[j],newq[r],i)>q_calc(newq[r],newq[r⑴],i))
newq[++r]=q[j];
} for(int j=1;j<=m;j++)
{ int ll=l+1,rr=r,ans=1; while(ll<=rr) { int mid=(ll+rr)>>1; if(q_calc(newq[mid],newq[mid⑴],i)<=2*j)ans=mid,ll=mid+1; else rr=mid-1;
}
dis[i][j]=min(get_dis(node(i,j),newq[ans]),dis[i][j]);
}
}
}
bool check(int x)
{
memset(f,0,sizeof(f));
queueque; if(dis[st.x][st.y]>=x)
que.push(st),f[st.x][st.y]=1; while(!que.empty())
{
node u=que.front();
que.pop(); for(int i=1;i<=4;i++)
{
node tmp;
tmp.x=u.x+xx[i],tmp.y=u.y+yy[i]; if(tmp.x<=0||tmp.x>n||tmp.y<=0||tmp.y>m)continue; if(dis[tmp.x][tmp.y]>=x&&!f[tmp.x][tmp.y])
{
f[tmp.x][tmp.y]=1;
que.push(tmp);
}
}
} return f[ed.x][ed.y];
} int main()
{ freopen("zab5ocen.in","r",stdin);
freopen("1514.out","w",stdout); scanf("%d%d",&n,&m);
scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y);
scanf("%d",&num); for(int i=1;i<=num;i++)cin>>pt[i];
init();
get_min_dis(); int l=0,r=n*n+m*m,ans; while(l<=r) { int mid=(l+r)>>1; if(check(mid))l=mid+1,ans=mid; else r=mid-1;
} printf("%d ",ans); fclose(stdin);fclose(stdout); return 0;
}
