Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

精度啊精度~二分+BFS,输出精度为3位,控制精度要为5位,贴代码

Posted by yzhw at 2010-08-06 01:28:31 on Problem 2253 and last updated at 2010-08-06 01:31:17
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator