洛谷 P2571 [SCOI2010]传送带

本文主要是介绍洛谷 P2571 [SCOI2010]传送带，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
题目描述

在一个 222 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 AB\text{AB}AB 和线段 CD\text{CD}CD。lxhgww 在 AB\text{AB}AB 上的移动速度为 PPP，在 CD\text{CD}CD 上的移动速度为 QQQ，在平面上的移动速度 RRR。现在 lxhgww 想从 A\text AA 点走到 D\text DD 点，他想知道最少需要走多长时间。
输入格式

第一行 444 个整数，表示 A\text AA 和 B\text BB 的坐标，分别为 AxA_xAx，AyA_yAy，BxB_xBx，ByB_yBy。

第二行 444 个整数，表示 C\text CC 和 D\text DD 的坐标，分别为 CxC_xCx，CyC_yCy，DxD_xDx，DyD_yDy。

第三行 333 个整数，分别是 PPP，QQQ，RRR。
输出格式

输出数据为一行，表示 lxhgww 从 A\text AA 点走到 D\text DD 点的最短时间，保留到小数点后 222 位。
输入输出样例
输入 #1

0 0 0 100

100 0 100 100

2 2 1

输出 #1

136.60

说明/提示

对于 100%100%100% 的数据，1≤Ax,Ay,Bx,By,Cx,Cy,Dx,Dy≤1031\le A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\le10^31≤Ax,Ay,Bx,By,Cx,Cy,Dx,Dy≤103，1≤P,Q,R≤101\le P,Q,R\le101≤P,Q,R≤10。

代码：

#include<bits/stdc++.h>
using namespace std;
struct Point
{double x,y;
};const double eps=1e-6;
double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;double dist(double& ax, double& ay, double& bx, double& by)
{return sqrt((ax-bx)*(ax-bx) + (ay-by) * (ay-by));
}Point FD_solve(double& ex, double& ey, Point& c, Point& d)
{double lx = c.x, ly = c.y;double rx = d.x, ry = d.y;while(dist(lx, ly, rx, ry) > eps){double mid_x = (rx - lx) / 3;double mid_y = (ry - ly) / 3;double F_lx = lx + mid_x, F_rx = rx - mid_x;double F_ly = ly + mid_y, F_ry = ry - mid_y;double res_l = dist(ex, ey, F_lx, F_ly) / r + dist(F_lx, F_ly, d.x, d.y) / q;double res_r = dist(ex, ey, F_rx, F_ry) / r + dist(F_rx, F_ry, d.x, d.y) / q;if (res_r - res_l > eps){rx = F_rx;ry = F_ry;}else{lx = F_lx;ly = F_ly;}}Point F{lx, ly};return F;
}double AE_solve(Point& a, Point& b, Point& c, Point& d)
{double lx = a.x, ly = a.y;double rx = b.x, ry = b.y;while(dist(lx, ly, rx, ry) > eps){double mid_x = (rx-lx) / 3;double mid_y = (ry - ly) / 3;double E_lx = lx + mid_x, E_rx = rx - mid_x;double E_ly = ly + mid_y, E_ry = ry - mid_y;Point F_l = FD_solve(E_lx, E_ly, c, d);Point F_r = FD_solve(E_rx, E_ry, c, d);double res_l = dist(a.x, a.y, E_lx, E_ly) / p // AE+ dist(E_lx, E_ly, F_l.x, F_l.y) / r // EF+ dist(F_l.x, F_l.y, d.x, d.y) / q; // FDdouble res_r = dist(a.x, a.y, E_rx, E_ry) / p // AE+ dist(E_rx, E_ry, F_r.x, F_r.y) / r // EF+ dist(F_r.x, F_r.y, d.x, d.y) / q; // FDif (res_r - res_l > eps){rx = E_rx;ry = E_ry;}else{lx = E_lx;ly = E_ly;}}Point F = FD_solve(lx, ly, c, d);return dist(a.x, a.y, lx, ly) / p // AE+ dist(lx, ly, F.x, F.y) / r // EF+ dist(F.x, F.y, d.x, d.y) / q;
}int main()
{ios::sync_with_stdio(false);while(cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r){Point A{ax,ay};Point B{bx, by};Point C{cx, cy};Point D{dx, dy};double ans = AE_solve(A,B,C,D);cout<<fixed<<setprecision(2)<<ans<<endl;}return 0;
}