@(BZOJ)[三分法]
Description
在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。
两条传送带分别为线段AB和线段CD。
lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。
现在lxhgww想从A点走到D点，他想知道最少需要走多长时间。
Input
输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By。
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy。
第三行是3个整数，分别是P，Q，R。
Output
输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位
Sample Input
0 0 0 100
100 0 100 100
2 2 1
Sample Output
136.60
HINT
对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10
Solution
三分套三分.
就當是練一下手吧.
#include<cstdio>
#include<cmath>
#include<ctime>
#define hKReporter main
using namespace std;
struct vertex
{
double x, y;
inline void getInput()
{
scanf("%lf%lf", &x, &y);
}
}a, b, c, d;
double p, q, r;
inline double getThatJunk(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
inline double getDistance(double pro1,double pro2)
{
double x1, y1, x2, y2;
x1 = a.x + (b.x - a.x) * pro1, y1 = a.y + (b.y - a.y) * pro1;
x2 = c.x + (d.x - c.x) * pro2, y2 = c.y + (d.y - c.y) * pro2;
return getThatJunk(a.x, a.y, x1, y1) / p + getThatJunk(x1, y1, x2, y2) / r + getThatJunk(x2, y2, d.x, d.y)/q;
}
double get(double x)
{
double L = 0, R = 1;
for(int i = 0; i < 1 << 10; i ++)
{
double mid1 = L + (R - L) / 3, mid2 = L + (R - L) / 3 * 2;
double k1 = getDistance(x, mid1), k2 = getDistance(x, mid2);
if(k1 < k2)
R = mid2;
else
L = mid1;
}
return getDistance(x, L);
}
int hKReporter()
{
#ifndef ONLINE_JUDGE
freopen("BZOJ1857.in", "r", stdin);
freopen("BZOJ1857.out", "w", stdout);
// Sleep(1);
#endif
a.getInput(), b.getInput(), c.getInput(), d.getInput();
scanf("%lf%lf%lf", &p, &q, &r);
double L = 0, R = 1;
for(int i = 0; i < 1 << 10; i ++)
{
double mid1 = L + (R - L) / 3, mid2 = L + (R - L) / 3 * 2;
double k1 = get(mid1), k2 = get(mid2);
if(k1 < k2)
R = mid2;
else
L = mid1;
}
printf("%.2lf", get(L));
}