題意:
給定1個(gè)網(wǎng)格圖，其中有1些壞點(diǎn)，要求使出發(fā)點(diǎn)到終點(diǎn)的路徑上的所有點(diǎn)到離該點(diǎn)最近的壞點(diǎn)的最小距離距離最大，求這個(gè)最大值。
解析:
讀完題明顯分為兩部份:
第1部份:預(yù)處理所有點(diǎn)到他最近的壞點(diǎn)的距離。
第2部份:2分最大距離bfs判定。
第2部份不用說吧？
主要就是卡在第1部份。
我們斟酌依照每列來計(jì)算每一個(gè)點(diǎn)的dis距離(即到他最近的壞點(diǎn)的距離)
明顯可以發(fā)現(xiàn)，對(duì)該列來講，每行都可能有1個(gè)到該列最近的點(diǎn)，并且我們發(fā)現(xiàn)，如果某1行有兩個(gè)壞點(diǎn)的話，假定分別為A，B，并且A到該列的距離最近，那末B明顯不會(huì)對(duì)這1列的dis有任何影響。
所以我們明顯可以在求之前預(yù)處理1下每行的如果存在壞點(diǎn)的那個(gè)最近的壞點(diǎn)的坐標(biāo)。
接下來，我們討論壞點(diǎn)k,l，設(shè)我們要更新的點(diǎn)是(x,y)
如果k優(yōu)于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
所以我們只需要按處理出來的壞點(diǎn)順序保護(hù)1個(gè)
X2k?X2l+2?x?Xl?2?x?XkYk?Yl+Yk+Yl遞增便可。
更新的時(shí)候每次在其中2分查找最后1個(gè)<=2y的。
復(fù)雜度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;
}
