「BZOJ3695」「FJ2014集训」滑行
Description
首长NOI惨跪，于是去念文化课了。现在，他面对一道物理题。
现在有一个小滑块可以在地面上滑行，地面上被划分成不同的区域，使得小滑块在不同的
区域内部有一个不同的速度上限。
小滑块在(0，0)点，我们现在要推动小滑块到目标点（x,y）。
地面上有N层区域，每层区域都是矩形，现在给你一个序列{Hi}表示每层区域的高度，覆盖的地面横坐标范围是0～X，第i个区域的限速是vi。
注： Y=Sigma(Hi) 其中i从1到N
其它的地方小滑块不允许进入。
现在我们要设计一个路线使得小滑块滑到目标点的用时最小。
Input
第一行两个整数，分别表示N、x。
第二行N个整数，第i个数表示Hi。。
第三行N个整数，第i个数表示Vi。
Output
一行一个整数，表示最小用时，保留到小数点后第三位。
Sample Input
1 5
5
1
5
1
Sample Output
7.071
HINT
N<=100,X<=1000,对于任意i,满足1<=i<=N-1,有Vi<V(i+1)
题解
根据费马光程原理，此题时间最短路径必定是一条光路。
二分。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> const double pi=acos(-1); #define inf 2000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } double ans; int n,x; int h[105],v[105]; double cal(double now) { double sum=0,tmp=0;; for(int i=1;i<=n;i++) { sum+=(double)h[i]/tan(now); tmp+=(double)h[i]/sin(now)/v[i]; now=pi/2-asin(sin(pi/2-now)*v[i+1]/v[i]); } ans=tmp; return sum; } int main() { //freopen("run.in","r",stdin); //freopen("run.out","w",stdout); n=read();x=read(); for(int i=1;i<=n;i++) h[i]=read(); for(int i=1;i<=n;i++) v[i]=read(); double l=0,r=pi/2; while(r-l>1e-12) { double mid=(l+r)/2; double t=cal(mid); if(t<=x)r=mid; else l=mid; } printf("%.3lf\n",ans); return 0; } |
Subscribe
计数器 9774909
OI 课件=>
OI 课件=>