这是个几何题目,图示如下:
( 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的条件)……