NOIPの模拟

题目

Description

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

Input

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By 第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy 第三行是3个整数，分别是P，Q，R

Output

输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位

Sample Input

0 0 0 100 100 0 100 100 2 2 1

Sample Output

136.60

Data Constraint

对于30%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10 1<=P,Q,R<=5 对于100%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000 1<=P,Q,R<=10

题目大意

现在我们有一个二维的平面，有一只人想要从A点走到D点，那只人在平面上，在AB这条线段上，在CD这条线段上有三个可能不同的速度，求从A点到D点所需要最短的距离

比赛时の想法

在草稿纸上比划了一会儿后，发现答案的路径是在AB和CD两条路线上都选择一个点，然后路径就是：A->第一个点->第二个点->D（当然，两个点都是有可能在线段的顶点上的）于是我就开始思考怎么确定两个点的位置，这是想到了GDOI的DAY1T1感觉有点像，但是不会很会打啊/(ㄒoㄒ)/~~于是开始想其他的方法，又想到了可以先以1位精度来找到最优的两个点，再以0.001位精度再找一次（第二次查找的范围是±1）这样就可以在 10002 的时间内解决这个问题了，虽然我觉得这个方法是可行的，但是又证明不了正确性，最后错了两个小细节，只拿了一部分的分数

正解

三分套三分，对于一个下凹的二次函数，我们任意选择两个点，分别为 xi,xj(i<j) 在二次函数上对应的y值为 yi,yj 那么有以下三种情况： 1: yi>yj ，此时函数的峰值在 xi的右边 2: yi<yj ，此时函数的峰值在 xj的左边 3: yi=yj ，此时函数的峰值在 xi和xj之间 其实对于一个上凹的单峰函数也是一样的，证明的话就不做了，省得画图伤了你们的眼睛(〃＞皿＜)

贴代码

var ax,ay,bx,by,cx,cy,dx,dy,p,q,r,i,j,k,l,t1,t2,t3,t4:longint; x,y,x1,y1,k1,k2,b1,b2,ans,tot,ii,jj:extended; begin readln(ax,ay,bx,by); readln(cx,cy,dx,dy); readln(p,q,r); if ax=bx then k1:=0 else k1:=(ay-by)/(ax-bx); b1:=ay-k1*ax; if cx=dx then k2:=0 else k2:=(cy-dy)/(cx-dx); b2:=cy-k2*cx; if (k1=0) or (k2=0) then begin l:=ax; ax:=ay; ay:=l; l:=bx; bx:=by; by:=l; l:=cx; cx:=cy; cy:=l; l:=dx; dx:=dy; dy:=l; if ax=bx then k1:=0 else k1:=(ay-by)/(ax-bx); b1:=ay-k1*ax; if cx=dx then k2:=0 else k2:=(cy-dy)/(cx-dx); b2:=cy-k2*cx; end; ans:=9999999; if ax>bx then begin t1:=bx; t2:=ax; end else begin t1:=ax; t2:=bx; end; if cx>dx then begin t3:=dx; t4:=cx; end else begin t3:=cx; t4:=dx; end; for i:=t1 to t2 do begin for j:=t3 to t4 do begin x:=k1*i+b1; y:=k2*j+b2; tot:=sqrt((i-ax)*(i-ax)+(x-ay)*(x-ay))/p; tot:=tot+sqrt((j-i)*(j-i)+(y-x)*(y-x))/r; tot:=tot+sqrt((dx-j)*(dx-j)+(dy-y)*(dy-y))/q; if tot<ans then begin x1:=i; y1:=j; ans:=tot; end; end; end; ii:=x1-1; while ii<=x1+1 do begin ii:=ii+0.001; if ii<t1 then continue; if ii>t2 then break; x:=k1*ii+b1; for k:=-1000 to 1000 do begin jj:=y1+k/1000; if jj<t3 then continue; if jj>t4 then break; y:=k2*jj+b2; tot:=sqrt((ii-ax)*(ii-ax)+(x-ay)*(x-ay))/p; tot:=tot+sqrt((jj-ii)*(jj-ii)+(y-x)*(y-x))/r; tot:=tot+sqrt((dx-jj)*(dx-jj)+(dy-y)*(dy-y))/q; if tot<ans then ans:=tot; end; end; writeln(ans:0:2); end.