抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

洛谷P2571 传送带

题意简述

求从A点到D点的最短时间。

输入:

  • A、B、C、D这4个点的坐标。
  • 在AB上的速度 $P$、在CD上的速度 $Q$、在平面的移动速度 $R$。

输出:

  • 输出最短时间。
  • 保留两位小数。

题目分析

首先来看看样例。

点 E 为线段 AB 上的任意一点,点 F 为线段 CD 上的任意一点,从 A 到 D 所用时间最短的路线显然就是 $\frac{AE}{P}+\frac{DF}{Q}+\frac{EF}{R}$ 的最小值。

草图

假如 E 是定点,那么要找最优的 F 点,很容易就能想到三分。

而现在 E 点也是动点,所以我们对点 E 也使用三分,即三分套三分,这样即可找到最优解。

那么该如何进行三分呢?

首先三分需要 $midl$ 和 $midr$ ,这里使用的 $midl$、$midr$ 有些特别。为了便于计算距离以及对区间进行三等分,需要记录点的坐标,当 $midl$ 与 $midr$ 横纵坐标都相同时才停止三分。为了避免 B 在 A 的左边这样的问题,在做减法的时候需要使用fabs

在寻找点 E 的时候,缩小范围时判断 $midl$ 与 $midr$ 哪个能找到更优的 F,而在寻找点 F 时,缩小范围则要判断哪个所用的时间最少。

详情请见代码:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
double ax, ay, bx, by, cx, cy, dx, dy; //A、B、C、D点的坐标
double P, Q, R; //速度
inline double getDis(double x1, double y1, double x2, double y2) //用于获取两点距离
{
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
inline double getTime(double x1, double y1, double x2, double y2) //获取所需的时间
{
double a = getDis(x1, y1, ax, ay); //E点到A点的距离
double b = getDis(x2, y2, dx, dy); //F点到D点的距离
double c = getDis(x1, y1, x2, y2); //E点到F点的距离
return a / P + b / Q + c / R; //计算时间
}
double searchCD(double xx, double yy) //枚举CD上的点F
{
double lx, rx, ly, ry; //当前左右端点的横纵坐标
double midlx, midrx, midly, midry; //即midl和midr的横纵坐标
lx = cx, rx = dx, ly = cy, ry = dy; //左边界设置为C的坐标,右边界设置为D的坐标
while (fabs(rx - lx) > 1e-10 or fabs(ry - ly) > 1e-10) //横纵坐标都相同才停止
{
/*三等分横纵坐标*/
midlx = lx + (rx - lx) / 3.f;
midrx = rx - (rx - lx) / 3.f;
midly = ly + (ry - ly) / 3.f;
midry = ry - (ry - ly) / 3.f;

if (getTime(xx, yy, midlx, midly) < getTime(xx, yy, midrx, midry)) //左边的的更优就向左
{
rx = midrx;
ry = midry;
}
else //否则向右
{
lx = midlx;
ly = midly;
}
}
return getTime(xx, yy, midlx, midry); //返回当前的最优解
}
double searchAB() //枚举AB上的点E
{
double lx, rx, ly, ry; //当前左右端点的横纵坐标
double midlx, midrx, midly, midry; //即midl和midr的横纵坐标
lx = ax, rx = bx, ly = ay, ry = by; //左边界设置为A的坐标,右边界设置为B的坐标
while (fabs(rx - lx) > 1e-10 or fabs(ry - ly) > 1e-10) //横纵坐标都相同才停止
{
/*三等分横纵坐标*/
midlx = lx + (rx - lx) / 3.f;
midrx = rx - (rx - lx) / 3.f;
midly = ly + (ry - ly) / 3.f;
midry = ry - (ry - ly) / 3.f;

if (searchCD(midlx, midly) < searchCD(midrx, midry)) //左边的的更优就向左
{
rx = midrx;
ry = midry;
}
else //否则向右
{
lx = midlx;
ly = midly;
}
}
return searchCD(lx, ly); //返回得到的结果
}
int main()
{
/*输入*/
cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
cin >> P >> Q >> R;

/*输出*/
printf("%.2f\n", searchAB());
return 0;
}