题意:一个轮子上有安装一个测速器,已知起点s,终点f。当测速器经过S,F面的时候,开始计时和结束计时。问,对于确定的s,f,求最少的时间。
思路:对实际路程进行二分 等效于 对时间进行二分。可以对时间进行二分的原因:LimT→∞成立,LimT→0不成立。
那么对于确定的T,也就是确定的实际距离s。我们去判断,对于确定的s,我们能够跑的虚假距离是不是大于当前给定的路程dx。
求能够最大的虚假距离需要用到比较强的数学知识(其实就是高中的知识撒·-·!)
首先需要以下几点知识
1.cosx-cos(x+arfa)= Acosx+Bsinx 其中( A=1-cos(arfa) B=sin(arfa) ) 证明过程:直接三角函数展开,系数相同
2.对于Acos+Bsinx中(x∈[ 0,2*pi] )范围内,max(Acosx+Bsinx)=sqrt(A*A+B*B)。
3.圆周上的某一点水平距离移动了L,对应的圆心角转动的角度为L/R 。 证明过程: L= (sita/pi)*r 圆心角 就是初中的 L=n*pi*r/180° 那么转化成弧度制,pi/180°就转成了弧度制。
有了以上几点知识,可以讲思路啦!!(终于开始了,好艰难啊)
虚假距离的计算方式FAKE:FAKE=L - ( r-rcos(x+arfa) )+ r + rcosx=L + r*( cosx-cos(x+arfa) ) 见下面的图[我画了好久啊·-·! 其实就两分钟]
PS:这么用心能不能顶!=====( ̄▽ ̄*)我一下·-·!!!
CODE:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double r,v;
double a,b;
bool check(double l)
{
double arfa=l/r;
double A=r*(1-cos(arfa));
double B=r*sin(arfa);
return l+sqrt(A*A+B*B)>=b-a;
}
int main(void)
{
int n;
cin >> n >> r >> v;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a,&b);
double l=0,r=b-a,ans;
for(int i=1;i<=50;i++)
{
double mid=(l+r)/2.0;
if(check(mid))
ans=mid,r=mid;
else l=mid;
}
printf("%.10f\n",ans/v);
}
return 0;
}