Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
精度啊精度~二分+BFS,输出精度为3位,控制精度要为5位,贴代码Source Code Problem: 2253 User: yzhw Memory: 1020K Time: 0MS Language: G++ Result: Accepted Source Code # include <iostream> # include <cmath> # include <cstring> # include <cstdio> # include <queue> using namespace std; double dis[201][201]; int n; bool chk(double len) { bool used[201]; memset(used,0,sizeof(used)); queue<int> q; used[0]=true; q.push(0); while(!q.empty()) { int pos=q.front(); q.pop(); if(pos==1) return true; for(int i=0;i<n;i++) if(dis[pos][i]<=len+1e-8&&!used[i]&&i!=pos) { used[i]=true; q.push(i); } } return false; } int main() { int c=0; while(cin>>n) { double minnum=100000,maxnum=-1; if(!n) break; int p[201][2]; for(int i=0;i<n;i++) cin>>p[i][0]>>p[i][1]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j) { dis[i][j]=sqrt((double)(p[i][0]-p[j][0])*(p[i][0]-p[j][0])+(p[i][1]-p[j][1])*(p[i][1]-p[j][1])); if(dis[i][j]>maxnum) maxnum=dis[i][j]; if(dis[i][j]<minnum) minnum=dis[i][j]; } while(maxnum-minnum>1e-5) { double mid=(minnum+maxnum)/2; if(chk(mid)) maxnum=mid; else minnum=mid; } printf("Scenario #%d\nFrog Distance = %.3f\n\n",++c,maxnum); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator