题意：一个NxN的网格地板，有一些激光束从天花板垂直射向地面的某个网格，一个圆要安全地从左走到右，不碰到上边界，下边界以及激光束，问这个圆的直径最大能达到多大。
分析：可以二分直径，关键在check函数的写法。可以讲这个圆缩成一个点，把圆的直径转化为激光的扫描范围，当激光范围完全堵死一条通道的时候，这个直径则是不可行的。怎样判断是否堵死一条通道了呢。每次check(dis)的时候，枚举激光束对，如果激光束之间距离小于dis，那么它们两个之间建一条边。还要注意处理边界，如果激光束范围与上边界或下边界相交，那么边界与这个激光束也建一条边。最后从一个边界dfs到另一个边界，如果能够dfs到，那么说明此时通道被堵死，此dis是不行的。继续二分就能得到答案。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <string> #include <vector> using namespace std; #define N 5007 struct node { int x,y; }p[N]; double d[N][N]; vector<int> G[N]; int n,L; int vis[N],S,E; double dis(node ka,node kb) { return (double)sqrt((ka.x-kb.x)*(ka.x-kb.x)+(ka.y-kb.y)*(ka.y-kb.y)); } int dfs(int u,int fa) { if(u == E) return 1; vis[u] = 1; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(v == fa) continue; if(vis[v]) continue; if(dfs(v,u)) return 1; } return 0; } bool check(double D) { S = 0; E = L+1; for(int i=0;i<=L+1;i++) G[i].clear(); for(int i=1;i<=L;i++) { if(p[i].y < D) G[S].push_back(i); if(p[i].y + D > n) G[i].push_back(E); for(int j=i+1;j<=L;j++) { if(d[i][j] < D) { G[i].push_back(j); G[j].push_back(i); } } } memset(vis,0,sizeof(vis)); if(dfs(S,-1)) return 0; return 1; } int main() { int i,j; while(scanf("%d%d",&n,&L)!=EOF && n) { for(i=1;i<=L;i++) scanf("%d%d",&p[i].x,&p[i].y); for(i=1;i<=L;i++) for(j=i+1;j<=L;j++) d[i][j] = dis(p[i],p[j]); double low = eps; double high = n; while(low+eps < high) { double mid = (low+high)/2.0; if(check(mid)) low = mid; else high = mid; } printf("%.3lf\n",low); } return 0; }
UVALive 6168 Fat Ninjas --二分小数+搜索,布布扣,bubuko.com
UVALive 6168 Fat Ninjas --二分小数+搜索
原文：http://www.cnblogs.com/whatbeg/p/3900435.html
