这是个几何题目,图示如下:
         2210image.jpg
                                                     (       W       )
题目中已知X,Y,C(两线交点距地面的高度)求街道的宽度(w)。根据几何原理求得方程:1/c=1/sqrt((x*x-w*w)+1/sqrt((y*y-w*w))。这是个不能反解出w的隐方程(我试了很久,都没做出),所以要计算w的值就不能那么简单,所以我们就很快就想到“牛顿迭代法”,但这个方程的结构比较复杂(关键是我对牛顿迭代法不是很了解,呵呵),所以我选用了“二分迭代逼近求值”(我的一位学姐告诉我的,当时她这道题也没做,我告诉她这个公式,怎么样具体编程时,告诉我的,由二分搜索引出)。然后我根据她告诉我的思想做了一个,代码如下:

/*
  Name: 二分逼近求解
  Copyright:
  Author: LonelyTree

  Date: 15-08-08 11:03
  Description: 对方程w的二分逼近求解:1/c=1/ 1/sqrt((x*x-mid*mid))+1/sqrt((y*y-mid*mid))
*/


#include
< stdio.h >
#include
< math.h >

#define  EPS 0.000001
int  main( void )
{
    
double  x,y,c;
    
double  high,low,mid;
    
while (scanf( " %lf %lf %lf " , & x, & y, & c) == 3 )
    
{

        high
= x > y ? y:x;
        low
= 0.0 ;
        
while (high >= low)
        
{
           mid
= (high + low) / 2 ;
           
if ( 1 / c - 1 / sqrt((x * x - mid * mid)) - 1 / sqrt((y * y - mid * mid)) <= EPS)
           
{
                printf(
" %.3lf\n " ,mid);
                
break ;
           }

           
else   if ( 1 / c - 1 / sqrt((x * x - mid * mid)) - 1 / sqrt((y * y - mid * mid)) > EPS)
           
{
                low
= mid;
           }

           
else
           
{
               high
= mid;
           }


        }

        

    }

    
return   0 ;
}










呵呵,大家看看这段代码有什么问题。我当时做出了对提供的4组数据进行了测试,OK通过,然后高高兴兴去sumbit了,令我大吃一惊是个TLE,哇,心一下就阴了,话了很长时间做了个TLE的。然后回过头来仔细检查了一下,经几番思考,对代码进行如下处理,代码如下:

/*
  Name: 二分逼近求解
  Copyright:
  Author: LonelyTree

  Date: 15-08-08 11:03
  Description: 对方程w的二分逼近求解:1/c=1/ 1/sqrt((x*x-mid*mid))+1/sqrt((y*y-mid*mid))
*/


#include
< stdio.h >
#include
< math.h >

#define  EPS 0.000001
int  main( void )
{
    
double  x,y,c;
    
double  high,low,mid;
    
while (scanf( " %lf %lf %lf " , & x, & y, & c) == 3 )
    
{

        high
= x > y ? y:x;
        low
= 0.0 ;
        
while (high - low > EPS)
        
{
           mid
= (high + low) / 2 ;
           
if ( 1 / c > ( 1 / sqrt((x * x - mid * mid)) + 1 / sqrt((y * y - mid * mid))))
           
{
                low
= mid;
           }

           
else
           
{
                high
= mid;
           }


        }

        printf(
" %.3lf\n " ,mid);

    }

    
return   0 ;
}










然后又测了数据,sample过了,然后小心的去sumbit,这次对了,Accpected了哈!呵呵,现在请大家思考一下这两种代码的区别,为什么前一种是TLE的而后一种是AC的(问题就在while的条件)……