时间戳

首页 > 技术文章 > 【题解】 [SCOI2010]传送带 （三分法）

【题解】 [SCOI2010]传送带 （三分法）

Ning-Mew 2018-03-01 15:39 原文

题目描述

在一个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

Solution 

　　三分套三分。 

　　三分法是个很基础的东西，当问题的答案呈现出的函数图像是单峰的那么就可以使用三分法求出它的最值，具体操作与二分法差不多。 

　　可这道题为什么可以用三分法呢，也就是说它为什么是单峰的，我也不会= =，果断翻题解。 
　　

　　首先，我们用三分法，最基本的是要证明那个人一定是沿着如下路径走的：从A沿着AB走一段，再穿越到CD上某一点，最后到终点。证明如下：不妨假设p>q>r，因为当r>max(p,q)时没什么好讨论的，而p,q的大小没什么关系。那么假设这人从AB上一点X离开，那么如果它不沿着刚刚的路径，则它一定会沿着某个路径回到AB上一点Y，显然X->Y的最快方法是沿着AB走，因为这样距离最短而速度最快。证完。 
　　那么，如果我们假设它从AB上一点X出发到CD上一点Y再到终点，那么当X为定点时，时间与CY长度是成单峰函数的，证明如下： 
这里写图片描述
　　当s>=q时，显然时间随着CY的增大而减小，显然是单峰函数，因此不妨设s＜q。过点X作XH⊥CD，显然当Y在CH上时时间增大，不做讨论。当Y在HD上时，设XH=h，HY=t，那么Y点比D点的时间节约（当Y点比D点时间长时该式为负号）：t/q-(sqrt(t^2+h^2)-h)/s=t/q+h/s-sqrt(t^2+h^2)/s，显然sqrt(t^2+h^2)增长是没有t的增长快的，因此一开始该式为正数，时间减少；但是当t增大时，sqrt(t^2+h^2)的增大速度不断变快最终趋向于t的增大速度，不要忘了q>s，所以该式最终会变为负数并且一定会越变越小，时间不断增大。综上所述：时间先单调递减再单调递增，证完。 
　　然而我并不会证明从AB上一点X离开的最优时间，这个函数与AX成单峰函数关系。。。

　　于是就这样挖了个坑。。。最关键的地方还是没有讲到。

　　证明单调性貌似有点困难，但证明一边的凹函数还是不难的！

 

Code：

 1 //It is coded by Ning_Mew on 2.28
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<iostream>
 7 #include<algorithm>
 8 #define dd double
 9 using namespace std;
10 const dd cnt=0.00000001;
11 int ax,ay,bx,by,cx,cy,dx,dy;
12 int p,q,r;
13 dd dist(dd x1,dd y1,dd x2,dd y2){
14   return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
15 }
16 dd fabs(dd x){return x<0?-x:x;}
17 dd getans(dd x,dd y){
18   dd xl=cx,xr=dx,yl=cy,yr=dy;
19   dd x1,x2,y1,y2,t1,t2;
20   while(fabs(xl-xr)>cnt||fabs(yl-yr)>cnt){
21     x1=xl+(xr-xl)/3;  y1=yl+(yr-yl)/3;
22     x2=xl+(xr-xl)/3*2;y2=yl+(yr-yl)/3*2;
23     t1=dist(1.0*ax,1.0*ay,x,y)/p+dist(x,y,x1,y1)/r+dist(x1,y1,1.0*dx,1.0*dy)/q;
24     t2=dist(1.0*ax,1.0*ay,x,y)/p+dist(x,y,x2,y2)/r+dist(x2,y2,1.0*dx,1.0*dy)/q;
25     if(t1<=t2){xr=x2;yr=y2;}
26     else {xl=x1;yl=y1;}
27   }
28   return dist(1.0*ax,1.0*ay,x,y)/p+dist(x,y,xl,yl)/r+dist(xl,yl,1.0*dx,1.0*dy)/q;
29 }
30 
31 int main(){
32   scanf("%d%d%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
33   scanf("%d%d%d",&p,&q,&r);
34   dd x1,x2,y1,y2,t1,t2;
35   dd xl,xr,yl,yr;
36   xl=ax;yl=ay;xr=bx;yr=by;
37   while(fabs(xl-xr)>cnt||fabs(yl-yr)>cnt){
38     x1=xl+(xr-xl)/3;  y1=yl+(yr-yl)/3;
39     x2=xl+(xr-xl)/3*2;y2=yl+(yr-yl)/3*2;
40     t1=getans(x1,y1);t2=getans(x2,y2);
41     if(t1>t2){xl=x1;yl=y1;}
42     else {xr=x2;yr=y2;}
43   }
44   printf("%0.2f\n",getans(xl,yl));
45   return 0;
46 }

 

推荐阅读