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 |
二分搜索加DFS AC的,还有一定要注意不是.lf,而是.f 也不知知道是为什么,哈哈#include<vector> #include<cmath> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #define ll long long using namespace std; #define INF 0x3f3f3f3f int n,vis[220]; double mp[220][220],dis[220]; struct AX{ int x; int y; }point[220]; vector<double> mx[220]; double Get_dis(AX a,AX b){ int x=a.x-b.x,y=a.y-b.y; return sqrt(x*x*1.0+y*y*1.0); } bool DFS(int k,double v){ vis[k]=1; for(int i=1;i<=n;i++){ if(vis[i])continue; if(mp[k][i]>v)continue; else if(i!=2){ if(DFS(i,v)) return true;} else return true; } return false; } int main(){ int casen=1; while(scanf("%d",&n)==1&&n){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j)mp[i][j]=0.0; else mp[i][j]=INF*1.0; for(int i=1;i<=n;i++)scanf("%d%d",&point[i].x,&point[i].y); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=Get_dis(point[i],point[j]); double R=mp[1][2],L=0.0,mid; while(R-L>0.00001){ mid=(L+R)*1.0/2; memset(vis,0,sizeof(vis)); if(DFS(1,mid))R=mid; else L=mid; } printf("Scenario #%d\n",casen++); printf("Frog Distance = %.3f\n",mid); printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator