P2571 [SCOI2010]传送带 三分

题意：

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

范围&性质： (1le a_x,a_y,b_x,b_y,c_x,c_y,d_x,d_y le 10^3,1le p,q,rle 10)

分析：

题目相当于在(AB,CD)上分别求出一个点(E，F),使得(frac{dis(A,E)}{p}+frac{dis(E,F)}{r}+frac{dis(F,d)}{q})最小，我们画图可以发现，当(E)固定时，(F)的取值是一个单峰函数，所以我们可以三分，整体就是三分套三分

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	const double eps = 1e-6;
	double p,q,r;
	double ax,ay,bx,by,cx,cy,dx,dy;
	
	double dis(double x1,double y1,double x2,double y2)
	{
		return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	}
	
	double tridiv2(double ex,double ey)
	{
		double lx=cx,ly=cy,rx=dx,ry=dy;
		while(dis(lx,ly,rx,ry)>=eps)
		{
			double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;
			double lmidx=lx+tmpx,lmidy=ly+tmpy;
			double rmidx=rx-tmpx,rmidy=ry-tmpy;
			double lans=dis(ex,ey,lmidx,lmidy)/r+dis(dx,dy,lmidx,lmidy)/q;
			double rans=dis(ex,ey,rmidx,rmidy)/r+dis(dx,dy,rmidx,rmidy)/q;
			if(rans-lans>eps) rx=rmidx,ry=rmidy;
			else lx=lmidx,ly=lmidy;
		}
		return dis(ex,ey,lx,ly)/r+dis(dx,dy,lx,ly)/q;;
	}
	
	double tridiv1()
	{
		double lx=ax,ly=ay,rx=bx,ry=by;
		while(dis(lx,ly,rx,ry)>=eps)
		{
			double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;
			double lmidx=lx+tmpx,lmidy=ly+tmpy;
			double rmidx=rx-tmpx,rmidy=ry-tmpy;
			double lans=tridiv2(lmidx,lmidy)+dis(ax,ay,lmidx,lmidy)/p;
			double rans=tridiv2(rmidx,rmidy)+dis(ax,ay,rmidx,rmidy)/p;
			if(rans-lans>eps) rx=rmidx,ry=rmidy;
			else lx=lmidx,ly=lmidy;
		}
		return tridiv2(lx,ly)+dis(ax,ay,lx,ly)/p;
	}
	
	void work()
	{
		scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
		scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
		scanf("%lf%lf%lf",&p,&q,&r);
		printf("%.2lf",tridiv1());
	}
	
}

int main()
{
	zzc::work();
	return 0;
}