xmu 1125.越野车大赛

Description

TheBeet正在參加一场越野车大赛。比赛的场地如右图:共分三块。每一块地面的长宽均为N与M,但地表情况不同。越野车在这段路面上的最快速度也不同。

蓝色线表示TheBeet可能的行车路线。

比赛的要求是要求选手从比赛的场地左上角驾车至右下角。

TheBeet想知道假设他在全部路段都以最高速度行驶(不考虑加速阶段),最快能在多少时间内完毕比赛。

xmu 1125 越野车大赛(公式推导&&三分)(中等)-LMLPHP

Input

  输入数据的第一行为两个正整数N M(N<=3000,M<=1000),表示一块路面的长和宽。

  第二行为三个正整数S,S,S(0<S,S,S<=100)。从上至下依次表示各个路面上越野车的最快速度。

Output

  输出一个实数表示TheBeet最快能在多少时间内完毕比赛。请输出一个尽可能精确的数字,控制误差在±0.000001的内。

Sample Input

30 10

2 5 3

Sample Output

13.7427361525

Hint

  假设你的输出和结果的相差在0.000001之内,则觉得是正确答案。

思路:

这个题目不错。横线N上有两个点。先要确定第一个x1,x1可能为mid1或midmid1;1,以mid1为基准求第二个点     2,以midmid1为基准求第二个点。

比較两个结果再一次三分求极值。

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-7
int n,m;
int s1,s2,s3; double cal(double x,double y)
{
return sqrt(m*m+x*x)/s1+sqrt(m*m+y*y)/s2+sqrt(m*m+(n-x-y)*(n-x-y))/s3;
} int main()
{
cin>>n>>m;
cin>>s1>>s2>>s3;
double ans=0xfffffff;
double l=0,h=n,ll=0,hh=n;
double mid1,midmid1,mid2,midmid2;
double t1,t2,t11,t22;
while(h-l>eps)
{
mid1=(l+h)/2;
midmid1=(mid1+h)/2;
//ans1=cal(mid1);
//ans11=cal(midmid1);
ll=0,hh=n;
while(hh-ll>eps)
{
mid2=(ll+hh)/2;
midmid2=(mid2+hh)/2;
t11=cal(mid1,mid2);
t22=cal(mid1,midmid2);
if(t11<t22)
hh=midmid2;
else
ll=mid2;
}//计算mid1为基准的第二个点的位置
t1=cal(mid1,ll);
ll=0,hh=n;
while(hh-ll>eps)
{
mid2=(ll+hh)/2;
midmid2=(mid2+hh)/2;
t11=cal(midmid1,mid2);
t22=cal(midmid1,midmid2);
if(t11<t22)
hh=midmid2;
else
ll=mid2;
}
t2=cal(midmid1,ll);
if(t1<t2)
{
h=midmid1;ans=min(ans,t1);
}
else
{
l=mid1;ans=min(ans,t2);
}
}
printf("%.10lf\n",ans);
return 0;
}

05-11 19:22