題意:
給定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;
}
