题目链接:这里
题意:就是给你两条线段AB , CD ,一个人在AB以速度p跑,在CD上以q跑,在其他地方跑速度是r。问你从A到D最少的时间。
解法:
先三分AB上的点,再三分CD上的点即可。
证明:
设E在AB上,F在CD上。
令人在线段AB上花的时间为:f = AE / p,人走完Z和Y所花的时间为:g = EF / r + FD / q。
f函数是一个单调递增的函数,而g很明显是一个先递减后递增的函数。两个函数叠加,所得的函数应该也是一个先递减后递增的函数。故可用三分法解之。
//HDU 3400
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
struct point{
double x, y;
point(){}
point(double x, double y) : x(x), y(y) {}
}a, b, c, d, e, f;
int t;
double p, q, r;
double getdis(point a1, point b1){
return sqrt((a1.x - b1.x)*(a1.x - b1.x) + (a1.y - b1.y)*(a1.y - b1.y));
}
double cal(double alpha){
f.x = c.x + (d.x - c.x) * alpha;
f.y = c.y + (d.y - c.y) * alpha;
return getdis(f, d) / q + getdis(e, f) / r;
}
double sanfen2(double alpha){
e.x = a.x + (b.x - a.x) * alpha;
e.y = a.y + (b.y - a.y) * alpha;
double l = 0, r = 1.0, mid, midd, cost;
while(r - l > eps){
mid = (l + r) / 2;
midd = (mid + r) / 2;
cost = cal(mid);
if(cost <= cal(midd)) r = midd;
else l = mid;
}
return getdis(a, e) / p + cost;
}
double sanfen1(){
double l = 0.0, r = 1.0, mid, midd, ret;
while(r - l > eps){
mid = (l + r) / 2;
midd = (mid + r) / 2;
ret = sanfen2(mid);
if(ret <= sanfen2(midd)) r = midd;
else l = mid;
}
return ret;
}
int main()
{
int t;
scanf("%d", &t);
while(t--){
scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y);
scanf("%lf%lf%lf%lf", &c.x, &c.y, &d.x, &d.y);
scanf("%lf%lf%lf", &p, &q, &r);
printf("%.2f\n", sanfen1());
}
return 0;
}