首页 > 代码库 > UVALive 6168 Fat Ninjas --二分小数+搜索
UVALive 6168 Fat Ninjas --二分小数+搜索
题意:一个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 5007struct 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。