【P2571 [SCOI2010]传送带】题解

题目链接

题目

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

思路

三分套三分。

现在AB上三分一个点，再在CD上三分一个点，易证符合单调性。

求距离需要用到一些数学知识。

Code

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
//#define N
int n, m, i, j, k; 
double ax, ay, bx, by, cx, cy, dx, dy, p, q, r; 

double pingfa(double x)
{
	return x*x; 
}

double go(double lx, double ly, double rx, double ry, double speed)
{
	double s=sqrt(pingfa(rx-lx)+pingfa(ry-ly)); 
	return s/speed; 
}

double second_three_mid(double lstlx, double lstly)
{
	double lx, ly, rx, ry, tx, ty, nlx, nly, nrx, nry; 
	double lans, rans; 
	lx=cx; ly=cy; rx=dx; ry=dy; 
	while(abs(rx-lx)>1e-12||abs(ry-ly)>1e-12) 
	{
		
		tx=(rx-lx)/3; ty=(ry-ly)/3; 
		nlx=lx+tx; nly=ly+ty; 
		nrx=rx-tx; nry=ry-ty; 
		lans=go(lstlx, lstly, nlx, nly, q)+go(nlx, nly, dx, dy, r); 
		rans=go(lstlx, lstly, nrx, nry, q)+go(nrx, nry, dx, dy, r);
		// printf("> %lf %lf %lf %lf %lf %lf\n", lx, ly, rx, ry, lans, rans);  
		if(lans1e-12||abs(ry-ly)>1e-12)
	{
		// printf("> %lf %lf %lf %lf\n", lx, ly, rx, ry); 
		tx=(rx-lx)/3; ty=(ry-ly)/3; 
		nlx=lx+tx; nly=ly+ty; 
		nrx=rx-tx; nry=ry-ty; 
		lans=go(ax, ay, nlx, nly, p)+second_three_mid(nlx, nly); 
		rans=go(ax, ay, nrx, nry, p)+second_three_mid(nrx, nry); 
		// printf("\n%lf %lf %lf %lf %lf\n", nlx, nly, go(ax, ay, nlx, nly, p), second_three_mid(nlx, nly), lans); 
		// printf("\n%lf %lf %lf %lf %lf\n", nrx, nry, go(ax, ay, nrx, nry, p), second_three_mid(nrx, nry), rans); 
		if(lans