隐藏
「SCOI2010」传送带 - 三分套三分 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SCOI2010」传送带 - 三分套三分

题目大意

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


题目分析

不难发现答案一定是先在$AB$上走一段,然后走到$CD$,再在$CD$段上走到$D$。
设在$AB$上的$p_1$处脱离,在$CD$上的$p_2$上进入,则答案即可写作一个形似$f(p_1)+g(p_2)+d(p_1,p_2)$的函数。
这个函数当$p_1$确定时是一个单峰函数,在$p_2$确定的时候也是一个单峰函数,因此可以一次三分求出$p_1$,再套入一个三分计算$p_2$。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const double eps=1e-8;

struct Point {
double x,y;
Point(double x=0,double y=0):x(x),y(y) {}
} a,b,c,d;

double P,Q,R;

Point getp(Point a,Point b,double k) {return Point(a.x+(b.x-a.x)*k,a.y+(b.y-a.y)*k);}
double dist(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double Cal(Point _a,Point _d) {return dist(a,_a)/P+dist(d,_d)/Q+dist(_a,_d)/R;}

double Cal(Point p) {
double Left=0,Right=1;
while(Right-Left>eps) {
double lmid=Left+(Right-Left)/3,rmid=Right-(Right-Left)/3;
Point lp=getp(c,d,lmid),rp=getp(c,d,rmid);
if(Cal(p,lp)<Cal(p,rp))Right=rmid;
else Left=lmid;
}
return Cal(p,getp(c,d,(Left+Right)/2));
}

int main() {
a.x=Get_Int(),a.y=Get_Int();
b.x=Get_Int(),b.y=Get_Int();
c.x=Get_Int(),c.y=Get_Int();
d.x=Get_Int(),d.y=Get_Int();
P=Get_Int(),Q=Get_Int(),R=Get_Int();
double Left=0,Right=1;
while(Right-Left>eps) {
double lmid=Left+(Right-Left)/3,rmid=Right-(Right-Left)/3;
Point lp=getp(a,b,lmid),rp=getp(a,b,rmid);
if(Cal(lp)<Cal(rp))Right=rmid;
else Left=lmid;
}
printf("%0.2lf\n",Cal(getp(a,b,(Left+Right)/2)));
return 0;
}
姥爷们赏瓶冰阔落吧~