傳送帶
【題目描述】
在一個(gè)2維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段AB和線段CD。lxhgww在AB上的移動(dòng)速度為P，在CD上的移動(dòng)速度為Q，在平面上的移動(dòng)速度R。現(xiàn)在lxhgww想從A點(diǎn)走到D點(diǎn)，他想知道最少需要走多長時(shí)間
【輸入】
輸入數(shù)據(jù)第一行是4個(gè)整數(shù)，表示A和B的坐標(biāo)，分別為Ax，Ay，Bx，By
第二行是4個(gè)整數(shù)，表示C和D的坐標(biāo)，分別為Cx，Cy，Dx，Dy
第三行是3個(gè)整數(shù)，分別是P，Q，R
【輸出】
輸出數(shù)據(jù)為一行，表示lxhgww從A點(diǎn)走到D點(diǎn)的最短時(shí)間，保留到小數(shù)點(diǎn)后2位
【樣例輸入】
0 0 0 100
100 0 100 100
2 2 1
【樣例輸出】
136.60
【數(shù)據(jù)范圍】
對(duì)于100%的數(shù)據(jù)，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10
====================================================================
路線一定是從A出發(fā)，在AB上走一段到E，然后從E走到CD上的一點(diǎn)F，然后從F走到D。
。。其實(shí)這就光的折射。。但無奈物理不強(qiáng)。。。
如果固定E點(diǎn)，很容易看出來F在CD上連續(xù)移動(dòng)時(shí)，用時(shí)關(guān)于F位置是單峰的，或者是寫出用時(shí)關(guān)于F位置的函數(shù)也可以發(fā)現(xiàn)是單峰的。。
于是hyf神牛采取了他說的“惡搞”方法：枚舉AB上的點(diǎn)，在CD上三分。。AC
sonic又發(fā)現(xiàn)了其實(shí)如果把總時(shí)間看做E在AB上的位置的函數(shù)，這個(gè)也是單峰的。。。于是在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