大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
计算几何+SPFA
我已经不想看我的提交记录了。。。。
HDU 我起码WA了2页。。。。
都是浮点数惹的祸。
const double eps=1e-4; abs(a-b)<=eps;
这样来推断相等。
总共 n 条鳄鱼,最多有 n*(n+1)/2 条路。
抽象化处理。
把 中心的起点当作 起点0 ; 最多有 n+1 条路。
把鳄鱼和周围的边界的终点都当作 n+1 ; 最多有 n+1 条
总共就仅仅存在 n+2个点。
就是计算0 和 n+1 的最短距离。
有个小优化,就是当 跳跃距离可以直接跳到岸上的时候就直接输出 42.5 1;
G++ ,C++ 都过了。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<cmath> #include<algorithm> #include<queue> #include<map> #include<iostream> using namespace std; const double INF= 0xfffffff; bool vis[103]; double dis[103]; int path[103]; int n; double m; const double eps=1e-4; struct lx { int v; double len; }; vector<lx>g[103]; struct node { double x,y; } point[101]; void build() { int u,v; for(int i=1; i<=n; i++) { double x=point[i].x; double y=point[i].y; double len; u=i; double xx,yy; lx now; xx=min(50.00-x,50.00-y); yy=min(50.00+x,50.00+y); len=min(xx,yy); if(len<=m) { now.v=n+1,now.len=len; g[u].push_back(now); } len=sqrt(x*x+y*y); if(len-7.5<=m) { now.len=len-7.5; now.v=u; g[0].push_back(now); } for(int j=i+1; j<=n; j++) { len=sqrt((x-point[j].x)*(x-point[j].x)+(y-point[j].y)*(y-point[j].y)); if(len<=m) { now.len=len; now.v=j; g[u].push_back(now); now.v=u; g[j].push_back(now); } } } } void SPFA() { for(int i=0; i<103; i++) dis[i]=INF,vis[i]=0,path[i]=INF; queue<int>q; dis[0]=0,vis[0]=1; q.push(0);path[0]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int j=0; j<g[u].size(); j++) { int v=g[u][j].v; double len=g[u][j].len; if(abs(dis[v]-dis[u]-len)<=eps) { if(path[v]>path[u]+1) path[v]=path[u]+1; } else if(dis[v]>=dis[u]+len) { dis[v]=dis[u]+len; path[v]=path[u]+1; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(abs(dis[n+1]-INF)<=eps) puts("can't be saved"); else printf("%.2f %d\n",dis[n+1],path[n+1]); } int main() { while(cin>>n>>m) { for(int i=0; i<103; i++) g[i].clear(); for(int i=1; i<=n; i++) scanf("%lf%lf",&point[i].x,&point[i].y); if(m>=42.50) { puts("42.50 1"); continue; } build(); SPFA(); } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117989.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...