一道算法分析题目,求交流

2. 赶公交
Alfred在大学新区上学,他每个星期都要到市区学琴,因此要在每个星期六的10点钟之前赶到琴行上课,从郑大坐68路车到琴行要花整整一个小时,而68路车是每半小时一趟,整点和30分的时候会发一趟车。
这一次,Alfred起床晚了,一看表已经8点多了,匆忙收拾了一下之后,Alfred马上冲向公交站,但是,由于路况不佳,在前面的一段路上满是泥泞。路况如下:

如左图,A(xA,yA)是Alfred现在所处的位置,B(xB,yB)是公交站(Bus-stop)的位置,其中y>0的区域是泥泞的地面,Alfred在泥泞的地面上的移动速度是v1(米/秒),而y<0的区域是水泥地,Alfred在水泥地上的移动速度只有v2(米/秒),其中v1<=v2,A在第二象限,B在第四象限。
Alfred是一个物工院的学生,他稍微估算了一下,剩下的时间已经不多了,他看看表,现在离9点整只剩下T秒了 (T由题目给出),Alfred想知道,他如果用最优的策略赶往公交站,今天的课是否会迟到。
  输入规格:
第一行是一个整数C,C<=10,紧接着C组数据,每组数据依次给出xA,yA,xB,yB,v1,v2 和T,他们的意义如上文所述,x,y坐标的单位是米,所有坐标的绝对值<109,T是一个整数。
  输出规格:
对于每组数据,输出YES或NO,表示Alfred会不会迟到。

作者: yuanyingfeiyu   发布时间: 2011-06-06

求指教啊求指教,我的想法是利用光学上的一个结论,即光总是走花费时间最少的路径,这个题目的模型满足光学中折射的模型,但是在求解过程中还是遇到了困难,要解四次方程,还求高手指教

作者: yuanyingfeiyu   发布时间: 2011-06-06

耗时最短的点,应该在线段(xA,0)和(xB,0)之间,
你用折半迭代的办法“试”出折射点,即耗时最短的那个交点如何?

作者: fengzhw   发布时间: 2011-06-06