题解：#8757.作画机器 - 帖子

这道题一看的数据范围第一眼想到的应该是暴力枚举

即对于条线段枚举所有的绘制顺序可能

目前比较常见的枚举排列的方式有和全排列函数 next_permutation 有兴趣的同学可以百度自行学习

如果能够想到使用来枚举那么这道题的难度就是最基础的模板

在枚举之前首先得解决两点直接的距离计算

由于本题需要保留位小数，所以如果为了保险起见可以使用 long double 类型，不过 double 也够用

欧几里得距离：

double distance(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

在使用枚举的时候要注意，由于每段线段都有两个点所以我们既可以从起点到终点也可以从终点到起点

#include <bits/stdc++.h>
using namespace std;

struct LineSegment {
    int x1, y1, x2, y2;  // 线段的两个端点
};

double S, T;  // 非作画速度和作画速度
double min_time = 1e12;  // 初始为一个较大的数，用于存储最小时间
vector<LineSegment> segments;  // 存储所有线段

// 计算两点之间的欧几里得距离
double distance(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// 深度优先搜索函数
void dfs(int current_x, int current_y, double current_time, int painted_count, vector<bool>& visited) {
    // 如果所有线段都绘制完，更新最小时间
    if (painted_count == segments.size()) {
        min_time = min(min_time, current_time);
        return;
    }

    // 遍历每个线段，尝试从两种方向绘制
    for (int i = 0; i < segments.size(); ++i) {
        if (!visited[i]) {
            visited[i] = true;

            // 从线段的第一个端点开始绘制
            double move_time = distance(current_x, current_y, segments[i].x1, segments[i].y1) / S;
            double draw_time = distance(segments[i].x1, segments[i].y1, segments[i].x2, segments[i].y2) / T;
            dfs(segments[i].x2, segments[i].y2, current_time + move_time + draw_time, painted_count + 1, visited);

            // 从线段的第二个端点开始绘制
            move_time = distance(current_x, current_y, segments[i].x2, segments[i].y2) / S;
            draw_time = distance(segments[i].x2, segments[i].y2, segments[i].x1, segments[i].y1) / T;
            dfs(segments[i].x1, segments[i].y1, current_time + move_time + draw_time, painted_count + 1, visited);

            visited[i] = false;  // 回溯
        }
    }
}

int main() {
    int n;
    cin >> n >> S >> T;

    segments.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> segments[i].x1 >> segments[i].y1 >> segments[i].x2 >> segments[i].y2;
    }

    vector<bool> visited(n, false);  // 用于记录哪些线段已经绘制
    dfs(0, 0, 0.0, 0, visited);  // 从 (0, 0) 开始绘制

    cout << fixed << setprecision(10) << min_time << endl;
    return 0;
}

题解：#8757.作画机器 审核通过

题解：#8757.作画机器审核通过