実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 694

問題概要

$xy$ 平面に対し、レーザを照射しながら線分を印字する印字機があります。印字開始時、レーザ照射位置は座標 $(0, 0)$ にある。

この印字機が線分を印字する際は、以下の流れに従う。

まず、レーザ照射位置を線分の端点のうちどちらか1つに移動させる。なお、どちらの端点から描画を始めてもよい。
その後、レーザ照射位置のある端点からもう一方の端点まで、レーザを照射しながらレーザ照射位置を一直線に移動させる。このとき、線分の途中で印字を中止することはできない。

また、レーザを照射していないとき、レーザ照射位置は1秒あたり速度 $S$ で任意の方向に移動でき、レーザを照射しているときは、レーザ照射位置は1秒あたり速度 $T$ で印字中の線分に沿って移動できる。

これからこの印字機で $N$ 本の線分を印字吸うことを考える。 $i$ 本目の線分は、座標 $(A_i, B_i)$ と座標 $(C_i, D_i)$ を結んでいる。なお、複数の線分が重なっていることがあるが、全ての線分についてその都度重なっている部分を印字しなければならない。うまく印字機を操作したとき、全ての線分を印字完了するまでにかかる最小の時間を求めよ。ただし、真の値との絶対誤差または相対誤差は、 $10^{-6}$ 以下であれば許容される。

制約

入力は全て整数。
$1 \leq N \leq 6$
$1 \leq T \leq S \leq 1000$
$-1000 \leq A_i,B_i,C_i,D_i \leq 1000$
長さ $0$ の線分は存在しない。

考察

この問題の特徴は、 $1 \leq N \leq 6$ と、制約が非常に小さいこと。点の数が最大で24個しかないので、印字パターンを全探索できそうだ。

全探索するうえで考える必要があるのは。

線分をどの順序で印字するか？
各線分をどちらの方向で印字するか？ $(A_i, B_i) \rightarrow (C_i, D_i) \: \mathrm{or} \: (C_i, D_i) \rightarrow (A_i, B_i)$

の2つ。前者は $N!$ 通り、後者は $2^N$ 通りある。

前者に関してはnext_permutationを使って順列全探索を、後者に関しては bit 全探索を用いることで効率的に全探索できる。

実装においては、Lineという構造体を使って $N$ 個の線分を管理した。また、順列全探索についてはorderという $1$ から $N$ までの線分の配列に対応するインデックスを格納し、それをnext_permutationで並び替えることで実現している。

コード

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

#define all(x) (x).begin(), (x).end()
#define fix(x) fixed << setprecision(x)
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr auto INF = 1e+9;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

struct Line
{
    int x1, y1, x2, y2;
};

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

int main()
{
    int N, S, T;
    cin >> N >> S >> T;
    vector<Line> lines(N);
    rep(i, 0, N) cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;

    vector<int> order(N);
    iota(all(order), 0);

    double ans = INF;
    do {
        rep(bit, 0, (1 << N)) {
            double sum = 0;
            int pos_x = 0, pos_y = 0;
            rep(i, 0, N) {
                if (bit & (1 << i)) {
                    sum += dist(pos_x, pos_y, lines[order[i]].x1, lines[order[i]].y1) / S;
                    pos_x = lines[order[i]].x2;
                    pos_y = lines[order[i]].y2;
                } else {
                    sum += dist(pos_x, pos_y, lines[order[i]].x2, lines[order[i]].y2) / S;
                    pos_x = lines[order[i]].x1;
                    pos_y = lines[order[i]].y1;
                }

                sum += dist(lines[order[i]].x1, lines[order[i]].y1, lines[order[i]].x2, lines[order[i]].y2) / T;
            }

            chmin(ans, sum);
        }
    } while (next_permutation(all(order)));

    cout << fix(12) << ans << endl;
}