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;
}