1. 题目

传送门=￣ω￣=

2. 题解

网上基本上所有 Dalao 都是写的 “三分套三分”Orz

（好像 WJMZBMR 写的是模拟退火，为啥我一开始写模拟退火挂了呢 QvQ 可能我太弱了）

先讲下这题吧。

首先 lxhgww 的路径一定是从 $A$点上传送带 $AB$，走 $x$个单位时间 ($0\leq x\leq \frac{AB}{P}$)，再下 $AB$传送带，徒步走上 $CD$传送带（不一定是在 $C$点上传送带），走 $y$个单位时间到达 $D$点 ($0\leq y\leq \frac{CD}{Q}$)

设用时为 $f(x,y)$（$x,y$的意义见上文）

则：

设 $f1(t)$表示从 $A$点出发，沿着 $AB$走 $t$个单位时间后到达的坐标。

设 $f2(t)$表示从 $D$点出发，沿着 $DC$走 $t$个单位时间后到达的坐标。

那么：

$$f(x,y)=\frac{dis(f1(x),f2(y))}{R} + x + y$$

（$dis$表示求两点之间的欧几里得距离）

好的，现在这个问题已经转化为了求一个二元函数的最小值

可以把函数放到三维空间里看成一个物体，要在一个矩形区域内找物体的最低点。

。。。

写挂模拟退火以后我就写了个粒子群优化算法。。。

这算法真 NB 啊，什么数学推导都不需要，完全把函数当做随机函数看都能过掉！

这个算法是模仿生物（鸟类）捕食的过程。把一堆粒子随机撒在函数定义域内，然后每次找出所有粒子中所在位置对应的函数值最优的粒子，并且让大家都尽量向这里加速。

每个粒子都是有自己的惯性的，这样可以增加随机性，以免卡在局部最优解导致答案错误。

总之就是模拟真实的自然界啦。。。

具体很难说清楚，可以去网上搜一下这个算法，很玄妙的 QvQ

但是好像网上很少有（或者说可能根本没有）把粒子群优化算法这种人工智能算法应用于 OI 竞赛的，所以这里发一下代码，里面会写上注释的，还是看代码比较好懂=。=（其实是手缝针啦打字有点不舒服）

另外实验结果表明，粒子群算法更注重粒子个数。。。像我一开始那样开 20 个粒子就冲上去爆〇的做法真的不可取 QvQ

代码：

#include <bits/stdc++.h>

#define BS (505)//粒子数组大小
#define eps (1e-8)

using namespace std;

const int cnt = 500;//粒子个数

struct vec//向量
{
    double x, y;
    vec operator + (const vec oth) const
    {
        return (vec){x + oth.x, y + oth.y};
    }
    vec operator - (const vec oth) const
    {
        return (vec){x - oth.x, y - oth.y};
    }
    vec operator * (const double d) const
    {
        return (vec){x * d, y * d};
    }
    vec operator / (const double d) const
    {
        return (vec){x / d, y / d};
    }
};

vec A, B, C, D, P1, P2;

double P, Q, R, rx, ry;

vec f1(double x) {return A + P1 * x;}//和上文定义的 f1 意义相同

vec f2(double x) {return D + P2 * x;}//和上文定义的 f2 意义相同

double Squ(double a) {return a * a;}

double dis(vec a, vec b)//求 a,b 的欧几里得距离
{
    return sqrt(Squ(a.x - b.x) + Squ(a.y - b.y));
}

double f(double x, double y)//和上文定义的 f 意义相同
{
    return x + y + dis(f1(x), f2(y)) / R;
}

double Rand() {return (double)rand() / RAND_MAX;}//返回一个 [0,1] 的随机实数

struct Bird {double vx, vy, x, y, f, pb, pbx, pby;} b[BS];//粒子们

//vx,vy 是速度向量，x,y 是位置向量，f 是当前位置的函数值，pb 是该粒子历史最优值

double w = 1, gb = 1e233, gbx, gby;

//w 是精度权重， gb 是全局目前最优值， gbx,gby 是取到全局最优值时的自变量 x,y

void Update(int a)//更新粒子 a 的状态，这里具体原理请见算法实现原理
{
    b[a].vx = b[a].vx * w + Rand() * w * (gbx + b[a].pbx - b[a].x * 2);
    b[a].vy = b[a].vy * w + Rand() * w * (gby + b[a].pby - b[a].y * 2);
    //b[a].v * w 是因为有惯性，另外的项则是尽量像更优解靠近
    b[a].x += b[a].vx, b[a].y += b[a].vy;//更新位置向量
    //下面 4 行是防止粒子出界，出界则反弹回来（这里我没在网上找到相关资料介绍如何处理出界，所以是自己 YY 的）
    if (b[a].x < 0) b[a].x = 0, b[a].vx = -b[a].vx;
    if (b[a].y < 0) b[a].y = 0, b[a].vy = -b[a].vy;
    if (b[a].x > rx) b[a].x = rx, b[a].vx = -b[a].vx;
    if (b[a].y > ry) b[a].y = ry, b[a].vy = -b[a].vy;
    b[a].f = f(b[a].x, b[a].y);//计算当前位置函数值
    if (b[a].f < b[a].pb)//更新局部最优解
        b[a].pbx = b[a].x, b[a].pby = b[a].y, b[a].pb = b[a].f;
}

int main(int argc, char const* argv[])
{
    scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y), P1 = B - A;
    scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y), P2 = C - D;
    scanf("%lf%lf%lf", &P, &Q, &R), srand(P + Q + R);
    rx = dis(B, A) / P, ry = dis(D, C) / Q;
    if (!rx) P1.x = P1.y = 0; else P1 = P1 / rx;//特判传送带是一个点的情况
    if (!ry) P2.x = P2.y = 0; else P2 = P2 / ry;
    for (int i = 1; i <= cnt; i += 1)//随机撒点
    {
        b[i].x = b[i].pbx = Rand() * rx, b[i].y = b[i].pby = Rand() * ry;
        b[i].f = b[i].pb = f(b[i].x, b[i].y);
        b[i].vx = b[i].vy = 0;
        if (gb > b[i].pb) gbx = b[i].pbx, gby = b[i].pby, gb = b[i].pb;
    }
    for (int p = 1; p <= 900; p += 1, w *= 0.99)//迭代 900 次，0.99 的 900 次方已经对答案无影响
        for (int i = 1; i <= cnt; i += 1)
            if (Update(i), gb > b[i].pb)
                gbx = b[i].pbx, gby = b[i].pby, gb = b[i].pb;//更新全局最优解
    printf("%.2f\n", gb);
    return 0;
}