Codeforces #364 C. Chris and Road
传送门：http://www.codeforces.com/contest/703/problem/C
题目翻译
一个凸多边形在初始给定的位置以恒定V的速度
在原点有个行人以最大u的速度上行
问行人最快到达(0,w)的时间
行人不能被凸多边形撞（行人点与凸多边形边重合不算被撞，只有行人进入凸多边形内部才算被撞）
题解
我们只需要考虑行人一开始冲过去和等车子过了之后再过两种情况。
对于每个凸多边形上的点，当它到达y轴时行人已经可以走到它的位置或更高，那么行人就不会被撞，如果所有点都满足即可直接冲过去。
如果不能冲，从低往高枚举凸多边形的点，计算尽量贴着凸多边形走/以全速搜的情况，就是答案。
代码
|
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 56 57 58 59 60 61 62 |
/* Author : WNJXYK Problem : C Blog : http://wnjxyk.cn Date : 2016 */ #include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<set> #include<vector> #include<map> using namespace std; const int Maxn=10000; int n,w,v,u; struct PNode{ int x,y; }; PNode p[Maxn+5]; inline bool cmp(PNode a,PNode b){ if (a.y<b.y) return true; if (a.y==b.y && a.x>b.x) return true; return false; } int main(){ //freopen("in.txt","r",stdin); scanf("%d%d%d%d",&n,&w,&v,&u); for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); bool flag = true; for (int i=1;i<=n;i++){ double pTime,cTime; pTime = (double)p[i].y / (double)u; cTime = (double)(p[i].x-0) / (double)v; //cout<<pTime<<" "<<cTime<<endl; if (pTime>cTime){ flag = false; break; } } if (flag){ printf("%.10lf\n",(double)w / (double)u); return 0; } sort(p+1,p+n+1,cmp); double Ans=0,rateY=0; p[0].y=-1; for (int i=1;i<=n;i++){ if (p[i].y==p[i-1].y) continue; if ( (double)(p[i].y-rateY) / (double)u + Ans < (double)p[i].x / (double) v ){ Ans = (double)p[i].x / (double) v; rateY = (double)p[i].y; } } Ans += ((double)w - rateY) / (double) u; printf("%.10lf\n",Ans); return 0; } |
原文链接：Codeforces #364 C. Chris and Road
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!