题意

• 两条传送带AB，CD，给出四个点坐标，在两条传送带和地面上的速度分别为P,Q,R,从A到D的最短时间是多少？

思路

• 从AB到CD某点花费满足凹函数，从AB某点到CD花费也满足凹函数，三分套三分

AC代码

#include<bits/stdc++.h>
using namespace std;
int P,Q,R;
const double eps=1e-7;
typedef struct{
	double x,y;
}dt;
dt A,B,C,D,E,F;

double dis(dt a,dt b){
	return sqrt(eps+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cal2(double a,double b){
	E.x = A.x + (b / dis(A,B)) * (B.x - A.x);
	E.y = A.y + (b / dis(A,B)) * (B.y - A.y);
	F.x = C.x + (a / dis(C,D)) * (D.x - C.x);
	F.y = C.y + (a / dis(C,D)) * (D.y - C.y);
	return (dis(C,D)-a)/Q+b/P+dis(E,F)/R;
}

double cal1(double a){
	double l=0,r=dis(D,C);
	int t=100;
	while(t--){
		double m1 = l + (r - l)/3;
		double m2 = r - (r - l)/3;
		if(cal2(m1,a)<cal2(m2,a)){
			r=m2;
		}else{
			l=m1;
		}
	}
	return cal2(l,a);
}

int main(){
	scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);
	scanf("%d%d%d",&P,&Q,&R);
	//三分套三分
	double l=0,r=dis(A,B);
	int t=100;
	while(t--){
		double m1=l+(r-l)/3;
		double m2=r-(r-l)/3;
		if(cal1(m1)<cal1(m2)){
			r=m2;
		}else{
			l=m1;
		}
	}
	printf("%.2lf\n",cal1(l));
	return 0;
}

PS

• 这个题真是极其恶心，把人都给debug傻了，注意计算各种距离即可