题目描述
在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间
输入输出格式
输入格式：
输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy
第三行是3个整数，分别是P，Q，R
输出格式：
输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位
输入输出样例
输入样例#1：
0 0 0 100
100 0 100 100
2 2 1
输出样例#1：
136.60
说明
对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000, 1<=P，Q，R<=10
Brave_Cattle sto backup_noob orz Brave_Cattle
backup_noob帮助Brave_Cattle调好了参数让暴力通过了此题.
一句话题意: 一个(1000*1000)的矩形中有(A,B,C,D)四个点.并且现在你在(A)点,要前往(D)点,并且在(AB,CD)上有传送带,在(AB),平地,(CD)上的速度分别为P,Q,R.问到达(D)的最小时间.
题解: 首先考虑在矩形中行进的路径.如果不走传送带,显然是直接走直线距离最短,如果要走传送带,也是直线上传送带需要走的平地路径最短.那么显然最终走的总距离就是(A)->(AB)上一点->(CD)上一点->(D).那么我们可以通过枚举得到(AB,CD)上这一点的位置,也就是将(AB)看作一个向量,则(vec {AP}=k*vec {AB}, k∈[0,1]),其中(P)为(AB)上的位置.因为本题精度要求不高,所以这样枚举是可以过的.
当然这题还有模拟退火,三分等算法.
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const double delta = 2e-4;
const int inf = 2147483647;
double ans = inf, P, Q, R;
struct point{
double x, y;
}a[10];
inline double dis(point a, point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline point get_pos(point a, point b, double k){
point temp; temp.x = (b.x-a.x)*k+a.x, temp.y = (b.y-a.y)*k+a.y;
return (point){ (b.x-a.x)*k+a.x, (b.y-a.y)*k+a.y };
}
inline double calc(double i, double j){
point temp1 = get_pos(a[1], a[2], i), temp2 = get_pos(a[3], a[4], j);
return dis(a[1], temp1)/P+dis(temp1, temp2)/R+dis(temp2, a[4])/Q;
}
int main(){
// freopen("walk.in", "r", stdin);
// freopen("walk.out", "w", stdout);
cin >> a[1].x >> a[1].y >> a[2].x >> a[2].y >> a[3].x >> a[3].y >> a[4].x >> a[4].y;
cin >> P >> Q >> R;
for(double i=0;i<=1;i+=delta)
for(double j=0;j<=1;j+=delta) ans = min(ans, calc(i, j));
cout << fixed << setprecision(2) << ans << endl;
return 0;
}
当然这题是可以用三分来做的.因为从一条直线到另一条直线的时间满足一个凸函数的性质.可以感性的理解一下:到直线的一端的无穷远的地方需要无限的时间,到另一端无穷远的地方也要无限时间,而到中间一个位置可以使时间最小,所以可以三分.
所以这里可以用一个三分套三分的方法,先三分在(AB)段走的长度,再三分在(CD)段走的长度.(虽然这里为什么三分套三分仍然是一个凸函数我并不是很懂,但是至少也可以枚举一边走的长度然后三分另一边).大概实现看一下代码吧.
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
double P, Q, R;
struct point{
double x, y;
}a[10];
inline double dis(point a, point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline point get(point a, point b, double k){
return (point){ (b.x-a.x)*k+a.x, (b.y-a.y)*k+a.y };
}
inline double calc(double k1, double k2){
point temp1 = get(a[1], a[2], k1), temp2 = get(a[3], a[4], k2);
return dis(a[1], temp1)/P+dis(temp1, temp2)/R+dis(temp2, a[4])/Q;
}
inline double check(double k){
double l = 0, r = 1;
while(r-l > eps){
double p1 = (2*l+r)/3, p2 = (l+2*r)/3;
if(calc(k, p1) > calc(k, p2)) l = p1;
else r = p2;
}
return calc(k, l);
}
int main(){
//freopen("data.in", "r", stdin);
cin >> a[1].x >> a[1].y >> a[2].x >> a[2].y;
cin >> a[3].x >> a[3].y >> a[4].x >> a[4].y;
cin >> P >> Q >> R;
double l = 0, r = 1;
while(r-l > eps){
double p1 = (2*l+r)/3, p2 = (l+2*r)/3;
if(check(p1) > check(p2)) l = p1;
else r = p2;
}
cout << fixed << setprecision(2) << check(l) << endl;
return 0;
}