由于我第一时间无法确定,在 上选点再到
上走是否满足凹函数,但我容易想到的是,当出发的一点确定的时候,走到
点这个函数是满足凹函数的!于是,将问题转换为:在
上选择确定的一点
,然后用三分计算该点出发到
点所需要花费的最小距离。
此时我们发动人类智慧!
注意到坐标轴的差值最大为 1000,我们可以设置一个比较小的步长,枚举在 上的点,然后再计算最小价值即可!
#include <iostream>
#include <cmath>
using namespace std;
#define lf double
#pragma GCC optimize(2)
const lf EPS = 1e-9;
struct Pos {
lf x, y;
};
struct Line {
lf K, B;
Line() {
}
Line(Pos a, Pos b) {
K = (a.y - b.y) / (a.x - b.x);
B = a.y - K * a.x;
}
lf get_y(lf x) {
return K * x + B;
}
};
inline lf POW(lf x) {
return x * x;
}
inline lf dis(Pos a, Pos b) {
return sqrt(POW(a.x - b.x) + POW(a.y - b.y));
}
Pos a, b, c, d;
lf sp, sq, sr;
//是否垂直
bool cdflag = false, abflag = false;
Line cd, ab;
inline lf get_dis(Pos star, Pos ed) {
return dis(star, ed) / sr + dis(ed, d) / sq;
}
//当 AB 线段上的出发点确定时,到达 D 的最短距离
inline lf get_val(Pos star) {
if (cdflag) { //cd垂直,枚举 Y 轴
lf l = min(c.y, d.y), r = max(c.y, d.y), lmid, rmid, mid;
lf L = l, R = r;
lmid = L, rmid = R;
while (r - l > EPS) {
//mid = (l + r) / 3.0;
lmid = max(L, (2 * l + r) / 3.0), rmid = min(R, (2 * r + l) / 3.0);
if (get_dis(star, { c.x, lmid }) <=
get_dis(star, { c.x, rmid })) r = rmid;
else l = lmid;
}
return min(get_dis(star, { c.x, lmid }),
get_dis(star, { c.x, rmid }));
} else { //cd不垂直
lf l = min(c.x, d.x), r = max(c.x, d.x), lmid, rmid, mid;
lf L = l, R = r;
lmid = L, rmid = R;
while (r - l > EPS) {
//mid = (l + r) / 3.0;
lmid = max(L, (2 * l + r) / 3.0), rmid = min(R, (2 * r + l) / 3.0);
if (get_dis(star, { lmid, cd.get_y(lmid) }) <=
get_dis(star, { rmid, cd.get_y(rmid) })) r = rmid;
else l = lmid;
}
return min(get_dis(star, { lmid, cd.get_y(lmid) }),
get_dis(star, { rmid, cd.get_y(rmid) }));
}
}
int main() {
cin >> a.x >> a.y >> b.x >> b.y;
cin >> c.x >> c.y >> d.x >> d.y;
cin >> sp >> sq >> sr;
lf ans = 9999999999;
if (fabs(c.x - d.x) < EPS) cdflag = true;
else {
cd = Line(c, d);
}
int cnt = 1;
//AB垂直
if (fabs(a.x - b.x) < EPS) {
abflag = true;
ans = min(get_val(a), get_val(b) + dis(a, b) / sp);
lf step = fabs(a.y - b.y) / (4e5 + 5e4);
lf symbol = a.y - b.y > EPS ? -1 : 1;
for (lf yy = a.y; cnt <= 450000; yy += symbol * step, cnt++) {
ans = min(ans, get_val({ a.x, yy }) + dis(a, { a.x, yy }));
}
} else {
ab = Line(a, b);
ans = min(get_val(a), get_val(b) + dis(a, b) / sp);
lf step = fabs(a.x - b.x) / (4e5 + 5e4);
lf symbol = a.x > b.x ? -1 : 1;
for (lf xx = a.x; cnt <= 450000; xx += symbol * step, cnt++) {
Pos pos = { xx, ab.get_y(xx) };
ans = min(ans, get_val(pos) + dis(a, pos) / sp);
}
}
printf("%.2lf", ans);
return 0;
}