【解题报告】洛谷 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]传送带](https://www.ctvol.com/wp-content/uploads/2021/05/20210516_60a0b92d7be24.jpg)
![【解题报告】洛谷 P2571 [SCOI2010]传送带](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
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("%.2fn",result); 118 return 0; 119 }
话说这个还是我第一次使用三分呢，以前都没有用过。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/606132.html