首页 > 代码库 > [FJSC2014]滑行
[FJSC2014]滑行
【题目描述】
首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题。
现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的区域内部有一个不同的速度上限。
小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)。
地面上有N层区域,每层区域都是矩形。现在给你一个序列{hi}表示每层区域的高度,覆盖的地面横坐标范围是0~x,第i个区域的限速是vi。
注:y=Σhi,其它的地方小滑块不允许进入。
现在我们要设计一个路线使得小滑块滑到目标点的用时最小。
【输入格式】
第一行两个整数,分别表示N,x。
第二行N个整数,第i个数表示hi。
第三行N个整数,第i个数表示vi。
【输出格式】
一行一个整数,表示最小用时,保留到小数点后第三位。
【样例输入】
1 5
5
1
【样例输出】
7.071
【数据范围】
N<=100,x<=1000,对于任意i:1<=i<N,有vi<vi+1
Solution
由于我以前查过费马原理,光路最速,所以就。。。。。。
就是一个二分,注意arcsin(x)中的|x|<=1,所以要把它倒着做。
1 #include<cstdio> 2 #include<cmath> 3 int n,m,h[110],v[110]; 4 double l,r,pi=3.14159265359,mid,t; 5 bool check(double a) 6 { 7 double x=0,tmp;t=0; 8 for(int i=1;i<=n;i++) 9 {10 x+=(tmp=h[i]*tan(a));11 t+=sqrt(h[i]*h[i]+tmp*tmp)/v[i];12 a=asin(v[i+1]*sin(a)/v[i]);13 }14 return x>m;15 }16 int main()17 {18 scanf("%d%d",&n,&m);int i;19 for(i=n;i;i--)scanf("%d",&h[i]);20 for(i=n;i;i--)scanf("%d",&v[i]);21 for(l=0,r=pi/2,i=1;i<=80;i++,check(mid=(l+r)/2)?r=mid:l=mid);22 printf("%.3lf\n",t);23 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。