BZOJ 1857

传送门

尼玛BZOJ刚刚又挂了好几个小时

自己YY一下,在每个传送带上不同位置时的答案一定是个单峰函数,有最优解,所以就用三分好了

先三分枚举其中一个传送带上的点,然后再套一个三分看看这个点在另一条传送带上的最优解如何,挑两个答案中比较近的更新三分的左右端点

注意这道题会出现AB两点重合的情况

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
program bzoj_1857;
const eps=1e-3;
type point=record x,y:extended; end;
var a,b,c,d,s1,s2,l,r:point;
v1,v2,v3:longint;
a1,a2,ans:extended;
function dis(a,b:point):extended;
begin
exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)));
end;
function calc(p:point):extended;
var l,r,s1,s2:point;
a1,a2:extended;
begin
l:=c;
r:=d;
repeat
s1.x:=l.x+(r.x-l.x)/3;
s1.y:=l.y+(r.y-l.y)/3;
s2.x:=r.x-(r.x-l.x)/3;
s2.y:=r.y-(r.y-l.y)/3;
a1:=dis(a,p)/v1+dis(p,s1)/v3+dis(s1,d)/v2;
a2:=dis(a,p)/v1+dis(p,s2)/v3+dis(s2,d)/v2;
if a1<a2 then r:=s2 else l:=s1;
until dis(l,r)<eps;
if a1<a2 then exit(a1) else exit(a2);
end;
begin
read(a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y);
read(v1,v2,v3);
l:=a;
r:=b;
ans:=maxlongint;
repeat
s1.x:=l.x+(r.x-l.x)/3;
s1.y:=l.y+(r.y-l.y)/3;
s2.x:=r.x-(r.x-l.x)/3;
s2.y:=r.y-(r.y-l.y)/3;
a1:=calc(s1);
a2:=calc(s2);
if a1<ans then ans:=a1;
if a2<ans then ans:=a2;
if a1<a2 then r:=s2 else l:=s1;
until dis(l,r)<eps;
writeln(ans:0:2);
end.