「SCOI2010」传送带 - 三分套三分

题目大意

    在一个$2$维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段$AB$和线段$CD$。lxhgww在$AB$上的移动速度为$P$，在$CD$上的移动速度为$Q$，在平面上的移动速度$R$。现在lxhgww想从$A$点走到$D$点，他想知道最少需要走多长时间。

---

题目分析

不难发现答案一定是先在$AB$上走一段，然后走到$CD$，再在$CD$段上走到$D$。
设在$AB$上的$p_1$处脱离，在$CD$上的$p_2$上进入，则答案即可写作一个形似$f(p_1)+g(p_2)+d(p_1,p_2)$的函数。
这个函数当$p_1$确定时是一个单峰函数，在$p_2$确定的时候也是一个单峰函数，因此可以一次三分求出$p_1$，再套入一个三分计算$p_2$。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const double eps=1e-8;

struct Point {
	double x,y;
	Point(double x=0,double y=0):x(x),y(y) {}
} a,b,c,d;

double P,Q,R;

Point getp(Point a,Point b,double k) {return Point(a.x+(b.x-a.x)*k,a.y+(b.y-a.y)*k);}
double dist(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double Cal(Point _a,Point _d) {return dist(a,_a)/P+dist(d,_d)/Q+dist(_a,_d)/R;}

double Cal(Point p) {
	double Left=0,Right=1;
	while(Right-Left>eps) {
		double lmid=Left+(Right-Left)/3,rmid=Right-(Right-Left)/3;
		Point lp=getp(c,d,lmid),rp=getp(c,d,rmid);
		if(Cal(p,lp)<Cal(p,rp))Right=rmid;
		else Left=lmid;
	}
	return Cal(p,getp(c,d,(Left+Right)/2));
}

int main() {
	a.x=Get_Int(),a.y=Get_Int();
	b.x=Get_Int(),b.y=Get_Int();
	c.x=Get_Int(),c.y=Get_Int();
	d.x=Get_Int(),d.y=Get_Int();
	P=Get_Int(),Q=Get_Int(),R=Get_Int();
	double Left=0,Right=1;
	while(Right-Left>eps) {
		double lmid=Left+(Right-Left)/3,rmid=Right-(Right-Left)/3;
		Point lp=getp(a,b,lmid),rp=getp(a,b,rmid);
		if(Cal(lp)<Cal(rp))Right=rmid;
		else Left=lmid;
	}
	printf("%0.2lf\n",Cal(getp(a,b,(Left+Right)/2)));
	return 0;
}