题意:平面上有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;
}