首页 > 其他 > 详细

#10017 传送带(SCOI 2010)(三分套三分)

时间:2018-08-20 22:28:50      阅读:203      评论:0      收藏:0      [点我收藏+]

【题目描述】

    在一个 2 维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段 AB 和线段 CD。lxhgww 在 AB上的移动速度为 P ,在 CD 上的移动速度为 Q,在平面上的移动速度 R。现在 lxhgww 想从 A 点走到 D 点,他想知道最少需要走多长时间。

【题目链接】

    https://loj.ac/problem/10017

【算法】

    猜想两条线段的最优点均满足单峰性质,于是三分套三分,代码借鉴黄学长。(http://hzwer.com/4255.html)

【代码】

    

 1 #include <bits/stdc++.h>
 2 #define eps 1e-4
 3 using namespace std;
 4 int ax,ay,bx,by;
 5 int cx,cy,dx,dy;
 6 int p,q,r;
 7 inline int read() {
 8     int x=0,f=1; char c=getchar();
 9     while(c<0||c>9){if(c==-) f=-1;c=getchar();}
10     while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}
11     return x*f;
12 }
13 double dis(double x1,double y1,double x2,double y2) {
14     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
15 }
16 double cal(double x,double y) {
17     double lx=cx,ly=cy,rx=dx,ry=dy;
18     double lmx,lmy,rmx,rmy,t1,t2;
19     while(fabs(lx-rx)>eps||fabs(ly-ry)>eps) {
20         lmx=lx+(rx-lx)/3,lmy=ly+(ry-ly)/3;
21         rmx=lx+(rx-lx)/3*2,rmy=ly+(ry-ly)/3*2;
22         t1=dis(x,y,lmx,lmy)/r+dis(lmx,lmy,dx,dy)/q;
23         t2=dis(x,y,rmx,rmy)/r+dis(rmx,rmy,dx,dy)/q;
24         if(t1>t2) lx=lmx,ly=lmy;
25         else rx=rmx,ry=rmy;
26     }
27     return dis(ax,ay,x,y)/p+dis(x,y,lmx,lmy)/r+dis(lmx,lmy,dx,dy)/q;
28 }
29 int main() {
30     ax=read(),ay=read(),bx=read(),by=read();
31     cx=read(),cy=read(),dx=read(),dy=read();
32     p=read(),q=read(),r=read();
33     double lx=ax,ly=ay,rx=bx,ry=by;
34     double lmx,lmy,rmx,rmy,t1,t2;
35     while(fabs(lx-rx)>eps||fabs(ly-ry)>eps) {
36         lmx=lx+(rx-lx)/3,lmy=ly+(ry-ly)/3;
37         rmx=lx+(rx-lx)/3*2,rmy=ly+(ry-ly)/3*2;
38         t1=cal(lmx,lmy),t2=cal(rmx,rmy);
39         if(t1>t2) lx=lmx,ly=lmy;
40         else rx=rmx,ry=rmy;
41     }
42     printf("%.2f\n",cal(lx,ly));
43     return 0;
44 }

 

#10017 传送带(SCOI 2010)(三分套三分)

原文:https://www.cnblogs.com/Willendless/p/9508334.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!