[模板]模拟退火/SCOI传送带

#include<bits/stdc++.h> 
 
using namespace std; 
 
// 定义一个类型别名pdd，它是一个pair<double, double>类型，用于表示二维平面上的点 
typedef pair<double,double> pdd; 
 
// 定义宏x和y，分别表示pair的第一个和第二个元素，方便访问点的坐标 
#define x first 
#define y second 
 
// 计算两点之间的欧几里得距离 
// 参数a和b是两个pdd类型的点 
// 返回值是两点之间的距离 
double dis(pdd a, pdd b) { 
    // 根据欧几里得距离公式计算距离，即sqrt((x1 - x2)^2 + (y1 - y2)^2) 
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); 
} 
 
// 计算从点a到点b，点c到点d的路径上，按照一定比例移动所需的总时间 
// 参数a和b表示第一条线段的起点和终点 
// 参数c和d表示第二条线段的起点和终点 
// 参数t表示在第一条线段上移动的比例 
// 参数s表示在第二条线段上移动的比例 
// 参数p表示在第一条线段上的移动速度 
// 参数q表示在第二条线段上的移动速度 
// 参数r表示从第一条线段上的某点到第二条线段上某点的移动速度 
// 返回值是总时间 
double caltime(pdd a, pdd b, pdd c, pdd d, double t, double s, double p, double q, double r) { 
    pdd e, f; 
    // 计算第一条线段上按照比例t的点e的坐标 
    e.x = a.x + (b.x - a.x) * t; 
    e.y = a.y + (b.y - a.y) * t; 
    // 计算第二条线段上按照比例s的点f的坐标 
    f.x = c.x + (d.x - c.x) * s; 
    f.y = c.y + (d.y - c.y) * s; 
    // 根据时间 = 距离 / 速度，计算总时间 
    return dis(a, e) / p + dis(e, f) / r + dis(f, d) / q; 
} 
 
// 生成一个[0, 1]之间的随机小数 
// 返回值是一个[0, 1]之间的随机小数 
double pro() { 
    // rand()函数生成一个随机整数，除以RAND_MAX得到一个[0, 1]之间的随机小数 
    return (double)rand() / RAND_MAX; 
} 
 
// 使用模拟退火算法求解从点a到点b，点c到点d的最短时间路径 
// 参数a和b表示第一条线段的起点和终点 
// 参数c和d表示第二条线段的起点和终点 
// 参数p表示在第一条线段上的移动速度 
// 参数q表示在第二条线段上的移动速度 
// 参数r表示从第一条线段上的某点到第二条线段上某点的移动速度 
// 返回值是最短时间 
double solve(pdd a, pdd b, pdd c, pdd d, double p, double q, double r) { 
    // 随机初始化第一条线段和第二条线段上的移动比例t和s 
    double t = pro(), s = pro(); 
    // 计算初始的总时间 
    double best = caltime(a, b, c, d, t, s, p, q, r); 
    // 模拟退火算法的初始温度 
    for (double temp = 1e5; temp > 1e-5; temp *= 0.999) { 
        // 在当前t的基础上，随机扰动得到新的t值，并确保在[0, 1]范围内 
        double nt = max(0.0, min(1.0, t + pro() * 0.2 - 0.1)); 
        // 在当前s的基础上，随机扰动得到新的s值，并确保在[0, 1]范围内 
        double ns = max(0.0, min(1.0, s + pro() * 0.2 - 0.1)); 
        // 计算新的总时间 
        double ntime = caltime(a, b, c, d, nt, ns, p, q, r); 
        // 如果新的总时间更短，或者满足一定的概率接受更差的解（模拟退火的特性） 
        if (ntime < best || exp(best - ntime) / temp > pro()) { 
            // 更新t和s的值 
            t = nt; 
            s = ns; 
            // 更新最短时间 
            best = min(best, ntime); 
        } 
    } 
    return best; 
} 
 
int main() { 
    // 初始化随机数种子，使用当前时间作为种子，确保每次运行程序时生成的随机数不同 
    srand(time(0)); 
 
    pdd a, b, c, d; 
    double p, q, r; 
    // 从标准输入读取第一条线段的起点和终点的坐标 
    cin >> a.x >> a.y >> b.x >> b.y; 
    // 从标准输入读取第二条线段的起点和终点的坐标 
    cin >> c.x >> c.y >> d.x >> d.y; 
    // 从标准输入读取三条路径的移动速度 
    cin >> p >> q >> r; 
 
    // 输出最短时间，保留两位小数 
    cout << fixed << setprecision(2) << solve(a, b, c, d, p, q, r) << endl; 
    return 0; 
}