OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2010】传送带

【题目描述】

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

【输入样例】

0 0 0 100

100 0 100 100

2 2 1

【输出样例】

136.60

【数据范围】

对于100%的数据,1<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000

1<=P,Q,R<=10

【题解】

膜拜随机神教OTL,模拟退火什么的到现在我还没去看呢……我只会不随机的办法……

很明显,最优的方案是在AB上找一点M,CD上找一点N,使得AM/p+ND/q+MN/r最小。假设点N确定了,即要使得AM/p+MN/r最小,易证符合条件的M有且只有一个,并且取AB上其他点得到的总时间和随着所取点和点M距离增大而增大,即AM/p+MN/r是单峰函数,可以用三分法求解。

现在考虑点N,对于每一个点N,都能对应的求得一个极值M,符合条件的N显然也只有一个,所以同理可目测这些极值与ND/q相加构成的函数也是单峰函数。最后的算法便是:先在CD上三分N,对于每一个三分点再在AB上三分求得其对应的极值M,三分套三分求解。

关于数学证明,我只会证AM/p+MN/r是单峰函数……

【代码】

说实话,三分比我想象的快很多0.0

http://paste.ubuntu.com/8017201/

评论

© OI技术宅 | Powered by LOFTER