欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【解题报告】洛谷 P2571 [SCOI2010]传送带

程序员文章站 2022-05-18 22:46:04
【解题报告】洛谷 P2571 [SCOI2010]传送带今天无聊,很久没有做过题目了,但是又不想做什么太难的题目,所以就用洛谷随机跳题,跳到了一道题目,感觉好像不是太难。 [CSDN链接](https://blog.csdn.net/Liang_Si_FFF/article/details/8457 ......

【解题报告】洛谷 p2571 [scoi2010]传送带
今天无聊,很久没有做过题目了,但是又不想做什么太难的题目,所以就用洛谷随机跳题,跳到了一道题目,感觉好像不是太难。

[csdn链接](https://blog.csdn.net/liang_si_fff/article/details/84570359)
[题目链接](https://www.luogu.org/problemnew/show/p2571)

===================================================================================
题目描述

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段ab和线段cd。lxhgww在ab上的移动速度为p,在cd上的移动速度为q,在平面上的移动速度r。现在lxhgww想从a点走到d点,他想知道最少需要走多长时间

 输入输出格式

输入格式:
输入数据第一行是4个整数,表示a和b的坐标,分别为ax,ay,bx,by

第二行是4个整数,表示c和d的坐标,分别为cx,cy,dx,dy

第三行是3个整数,分别是p,q,r

输出格式:
输出数据为一行,表示lxhgww从a点走到d点的最短时间,保留到小数点后2位

 输入输出样例

输入样例#1:
0 0 0 100
100 0 100 100
2 2 1
 输出样例#1:
136.60
说明

对于100%的数据,1<= ax,ay,bx,by,cx,cy,dx,dy<=1000

1<=p,q,r<=10

======================================================================================================

下面是我的分析过程


分析过程


首先,如图

【解题报告】洛谷 P2571 [SCOI2010]传送带

 


  1. 通过观察题目,我们可以发现,我们行走的路径一定是先在ab边上走,然后走下ab边,走向cd边,然后在cd边上走。(当然,有可能直接在a点就走下了ab边,也有可能直接从d点上了cd边,这里我们同样看作是先走下ab边,然后走上ab边)所以如果我们在ab边取一个点e,在cd边取一个点f,那么,不同的路径就可以用不同的e点和f点唯一表示,即每一个数对(e,f)都唯一对应一条路径(ps:e点可以和a或b重合,f点可以和c或者d重合)所以,我们可以想到一个朴素的算法:枚举e点和f点。但是这种算法明显是太暴力了,不可能通过的。
  2. 我们通过仔细思考,可以这么想:假如我现在的e点是已经确定好是哪个点的了,那么我们的问题就可以转换为:已知一条传送带,以及你在传送带上面的速度和地面上的速度,并且知道起点的准确位置,求到达终点的最短时间。
假如题目变成了这个样子,那么我们会发现,随着f点从c点到d点移动,这个总的时间应该是先递减后递增的。由于是一个单峰函数,所以我们可以用三分来做。
  3. 那么,我们现在的问题就是,这个e点也是移动的。但是我们现在能够做到对于ab边上的每一个点e,都能算出e点固定时的最短时间。所以,相比刚刚开始的同时枚举两个点e和f,现在只需要枚举一下e点就可以了。即:枚举e点的位置,然后对于每一个e点,对f点进行三分,找出每一个e点对应的最小路径的f点是哪一个。
  4. 但是,这个算法好像还是不太好,因为e点的枚举还是很麻烦的,复杂度一样很高。我们可以大胆猜想,或许e点的取值范围也是可以用三分法来做的!但是我还没有想到证明方法,也只是胡乱瞎猜。不过我猜对了。我还没有找到证明,找到证明之后我会再贴链接或者干啥的。
  5. 所以,我们现在可以得出一个能够在规定时间得出答案的算法:先三分e点的位置,对于每一个e点的位置,再三分f点的位置。
(细节注意:由于答案要保留小数点后两位,而地图的最大大小为1000,经过测试,1000乘于2/3大概乘那么30次就可以变得比0.01小,所以我们的三分大概只需要循环30次就可以了。不过我为了安全,循环了40次,反正没差多少。因此,e点需要三分40次,对于每一个e点,需要三分f点40*2次,大概就320次的样子。)
>事实上,这道题除了用三分的做法之外,好像还有什么其他做法,比如模拟退火算法, 但是我还没有学过。
ac代码如下

  1 #include<cstdio>
  2 #include<cmath>
  3 using namespace std;
  4 struct point
  5 {
  6 double x,y;
  7 point()
  8 {
  9 x=y=0;
 10 }
 11 };
 12 double m_abs(double a)
 13 {
 14 return a<0?-a:a;
 15 }
 16 int main()
 17 {
 18 point a,b,c,d;
 19 scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
 20 double p,q,r;
 21 scanf("%lf%lf%lf",&p,&q,&r);
 22 double result=100000000.0;
 23 point s1=a,s2=b,e1=c,e2=d;
 24 for(int i=1;i<=40;i++)
 25 {
 26 point s1,s2;
 27 s1.x=s1.x+(s2.x-s1.x)/3.0;
 28 s1.y=s1.y+(s2.y-s1.y)/3.0;
 29 s2.x=s2.x-(s2.x-s1.x)/3.0;
 30 s2.y=s2.y-(s2.y-s1.y)/3.0;
 31 double t1,t2;
 32 double x,y;
 33 x=m_abs(a.x-s1.x);
 34 y=m_abs(a.y-s1.y);
 35 t1=sqrt(x*x+y*y)/p;
 36 x=m_abs(a.x-s2.x);
 37 y=m_abs(a.y-s2.y);
 38 t2=sqrt(x*x+y*y)/p;
 39 e1=c;e2=d;
 40 double t3=10000000.0,t4=100000000.0;
 41 for(int j=1;j<=40;j++)
 42 {
 43 double t1,t2;
 44 point e1,e2;
 45 e1.x=e1.x+(e2.x-e1.x)/3.0;
 46 e1.y=e1.y+(e2.y-e1.y)/3.0;
 47 e2.x=e2.x-(e2.x-e1.x)/3.0;
 48 e2.y=e2.y-(e2.y-e1.y)/3.0;
 49 x=m_abs(s1.x-e1.x);
 50 y=m_abs(s1.y-e1.y);
 51 t1=sqrt(x*x+y*y)/r;
 52 x=m_abs(s1.x-e2.x);
 53 y=m_abs(s1.y-e2.y);
 54 t2=sqrt(x*x+y*y)/r;
 55 x=m_abs(d.x-e1.x);
 56 y=m_abs(d.y-e1.y);
 57 t1+=sqrt(x*x+y*y)/q;
 58 x=m_abs(d.x-e2.x);
 59 y=m_abs(d.y-e2.y);
 60 t2+=sqrt(x*x+y*y)/q;
 61 if(t1>=t2)
 62 {
 63 e1=e1;
 64 t3=t2<t3?t2:t3;
 65 }
 66 else
 67 {
 68 e2=e2;
 69 t3=t1<t3?t1:t3;
 70 }
 71 }
 72 e1=c;e2=d;
 73 for(int j=1;j<=40;j++)
 74 {
 75 double t1,t2;
 76 point e1,e2;
 77 e1.x=e1.x+(e2.x-e1.x)/3.0;
 78 e1.y=e1.y+(e2.y-e1.y)/3.0;
 79 e2.x=e2.x-(e2.x-e1.x)/3.0;
 80 e2.y=e2.y-(e2.y-e1.y)/3.0;
 81 x=m_abs(s2.x-e1.x);
 82 y=m_abs(s2.y-e1.y);
 83 t1=sqrt(x*x+y*y)/r;
 84 x=m_abs(s2.x-e2.x);
 85 y=m_abs(s2.y-e2.y);
 86 t2=sqrt(x*x+y*y)/r;
 87 x=m_abs(d.x-e1.x);
 88 y=m_abs(d.y-e1.y);
 89 t1+=sqrt(x*x+y*y)/q;
 90 x=m_abs(d.x-e2.x);
 91 y=m_abs(d.y-e2.y);
 92 t2+=sqrt(x*x+y*y)/q;
 93 if(t1>=t2)
 94 {
 95 e1=e1;
 96 t4=t2<t4?t2:t4;
 97 }
 98 else
 99 {
100 e2=e2;
101 t4=t1<t4?t1:t4;
102 }
103 }
104 t1+=t3;
105 t2+=t4;
106 if(t1>=t2)
107 {
108 s1=s1;
109 result=t2<result?t2:result;
110 }
111 else
112 {
113 s2=s2;
114 result=t1<result?t1:result;
115 }
116 }
117 printf("%.2f\n",result);
118 return 0;
119 }

 


话说这个还是我第一次使用三分呢,以前都没有用过。