注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3695][FJSC2014]滑行  

2014-07-20 21:11:56|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

【题目描述】

  首长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,所以要把它倒着做。


#include<cstdio>
#include<cmath>
int n,m,h[110],v[110];
double l,r,pi=acos(-1),mid,t;
bool check(double a)
{
double x=0,tmp;t=0;
for(int i=1;i<=n;i++)
{
x+=(tmp=h[i]*tan(a));
t+=sqrt(h[i]*h[i]+tmp*tmp)/v[i];
a=asin(v[i+1]*sin(a)/v[i]);
}
return x>m;
}
int main()
{
scanf("%d%d",&n,&m);int i;
for(i=n;i;i--)scanf("%d",&h[i]);
for(i=n;i;i--)scanf("%d",&v[i]);
for(l=0,r=pi/2,i=1;i<=80;i++,check(mid=(l+r)/2)?r=mid:l=mid);
printf("%.3lf\n",t);
}

  评论这张
 
阅读(63)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018