传送带
【题目描述】
在一个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
====================================================================
路线一定是从A出发，在AB上走一段到E，然后从E走到CD上的一点F，然后从F走到D。
。。其实这就光的折射。。但无奈物理不强。。。
如果固定E点，很容易看出来F在CD上连续移动时，用时关于F位置是单峰的，或者是写出用时关于F位置的函数也可以发现是单峰的。。
于是hyf神牛采取了他说的“恶搞”方法：枚举AB上的点，在CD上三分。。AC
sonic又发现了其实如果把总时间看做E在AB上的位置的函数，这个也是单峰的。。。于是在AB上三分后又在CD上三分。。AC
1
#include <iostream>
2#include <cmath>
3
4#define EPS (1e-8)
5
6using namespace std;
7
8
class Point
{
9
public:
10 double x,y;
11
Point(){}
12 Point(double _x, double _y):x(_x),y(_y){}
13 inline friend Point operator + (const Point a, const Point b){
14 return Point(a.x + b.x, a.y + b.y);
15
}
16 inline friend Point operator - (const Point a, const Point b){
17 return Point(a.x - b.x, a.y - b.y);
18 }
19 inline friend Point operator * (const Point a, const double b){
20 return Point(a.x * b, a.y * b);
21 }
22 double mo(){
23 return sqrt(x * x + y * y);
24 }
25
};
26Point A,B,C,D;
27double P,Q,R;
28void Init(){
29 scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
30 scanf("%lf%lf%lf%lf",&C.x,&C.y,&D.x,&D.y);
31 scanf("%lf%lf%lf",&P,&Q,&R);
32}
33
34double G(Point E, Point F){
35 return (A - E).mo() / P + (F - E).mo() / R + (D - F).mo() / Q;
36}
37
38double F(Point E){
39 Point b = C - D;
40 double l = 0, r = 1;
41 while (r-l>EPS){
42 double unit = (r - l) / 3.0;
43 double p = l + unit, q = r - unit;
44 double gp = G(E, b * p + D), gq = G(E, b * q + D);
45 if (gp > gq)
46 l = p;
47 else
48 r = q;
49 }
50 return G(E, b * l + D);
51}
52
53void Solve(){
54
55 double l = 0, r = 1;
56 Point a = B - A;
57 while (r-l>EPS){
58 double unit = (r - l) / 3.0;
59 double p = l + unit, q = r - unit;
60 double fp = F(a * p + A), fq = F(a * q + A);
61 if (fp > fq)
62 l = p;
63 else
64 r = q;
65 }
66 printf("%.2lf\n",F(a * l + A));
67}
68
69int main(){
70 freopen("walk.in","r",stdin);
71 freopen("walk.out","w",stdout);
72 Init();
73 Solve();
74 return 0;
75}
76