[SCOI2010]传送带 [三分法]

传送门

考虑先定一边, 即在AB上选x, 定义F(x) 为x到d的最短距离

最短距离为XH, 并且当且仅当P与M重合时最短,往左右都会变长, 于是F(x)为单峰函数, 当X确定时, 可以三分求解

又有 ans = min(dis(X,A)/Q + F(x)) , 可以证明ans 是单调的

令AB与ED交于F, ans = AF*sina - (sinb-sina)*AX. 但因为是在线段上而不是直线上,有很多限制条件, 我们继续三分求解

 顺便补充一下如何三分

 如果rmid的值大于lmid的值, 明显最小不在rmid--R之间, 我们将R定为rmid, 反之L为lmid

#include<bits/stdc++.h>
#define eps 1e-8
using namespace std;
struct Point{
	double x,y;
	Point(){};
	Point(double xx,double yy):x(xx),y(yy){};
	Point operator / (double a){return Point(x/a, y/a);}
	Point operator - (const Point &a){return Point(x-a.x, y-a.y);}
	Point operator + (const Point &a){return Point(x+a.x, y+a.y);}
}A,B,C,D;
double P,Q,R;
double dis(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double calc(Point X){
	Point l = C, r = D;
	while(dis(l,r) > eps){
		Point x = (r - l) / 3;
		Point lmid = l + x, rmid = r - x;
		double ans1 = dis(lmid,D)/Q + dis(X,lmid)/R;
		double ans2 = dis(rmid,D)/Q + dis(X,rmid)/R;
		if(ans2 - ans1 > eps) r = rmid;
		else l = lmid;
	} return dis(l,D)/Q + dis(X,l)/R;
}
double Solve(){
	Point l = A, r = B;
	while(dis(l,r) > eps){
		Point x = (r - l) / 3;
		Point lmid = l + x, rmid = r - x;
		double ans1 = calc(lmid) + dis(lmid, A)/P;
		double ans2 = calc(rmid) + dis(rmid, A)/P;
		if(ans2 - ans1 > eps) r = rmid;
		else l = lmid;
	} return calc(l) + dis(l,A)/P;
}
int main(){
	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("%0.2lf", Solve()); return 0;
}