题意:平面上有ABCD四个点,给定坐标,线段AB上的运动速度是P,线段CD上的运动速度是Q,其他平面内的运动速度是R,距离是欧几里得距离,求A从运动到D的最小值
链接:HDOJ3400
思路:计算几何的题,每次枚举,都会涉及到eps
想法很简单,要求A到D的最小值
如果最优解需要从AB线段上过的话,那么需要找到AB上的一个点X,使得AX+XD时间最短
同理,CD上需要找到一个Y,结合点X,AX+XY+YD的函数值最优
由于不清楚单调性,所以求X的时候是需要三分的,在三分之内,需要嵌套一个三分枚举Y,求得在该个X的情况下的最优值,然后比较X1和X2,利用三分原理删除一个区间,直到满足eps的限制
一定记得是:嵌套,不能直接两个while取最小值
代码:
#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-4
#define PI acos(-1.0)
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
struct point{
double x,y;
}A,B,C,D,LEFT,RIGHT,X,Y,LEFT2,RIGHT2;
double ans;
double P,Q,R;
int t;
double Sqr(double x){
return x*x;
}
double dist(point a,point b){
return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));
}
point middle(point a,point b){
point tmp;
tmp.x=(a.x+b.x)/2;
tmp.y=(a.y+b.y)/2;
return tmp;
}
point Add(point tmp,double add){
point ans;
ans.x=tmp.x+add;
ans.y=tmp.y+add;
return ans;
}
double calc2(point tmp){
return dist(X,tmp)/R+dist(tmp,D)/Q;
}
double calc(point tmp){
X=tmp;
//在CD上找一点Y,求XY+YD
LEFT2=C,RIGHT2=D;
point mid,mmid;
while(dist(LEFT2,RIGHT2)>eps){
mid=middle(LEFT2,RIGHT2);
mmid=middle(mid,RIGHT2);
if (calc2(mid)<calc2(mmid)) RIGHT2=Add(mmid,1e-6);
else LEFT2=Add(mid,-1e-6);
Y=mid;
}
return dist(A,X)/P+dist(X,Y)/R+dist(Y,D)/Q;
}
int main(){
//input;
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);
//在AB上找一点X,求AX+XD
LEFT=A,RIGHT=B;
point mid,mmid;
while(dist(LEFT,RIGHT)>eps){
mid=middle(LEFT,RIGHT);
mmid=middle(mid,RIGHT);
if (calc(mid)<calc(mmid)) RIGHT=Add(mmid,1e-6);
else LEFT=Add(mid,-1e-6);
X=mid;
}
printf("%.2lf\n",calc(X));
}
return 0;
}