AtCoder ABC 374 D - Laser Marking (2Q, 茶色, 350 点)

座標平面上の 本の線分の順序を探索して、さらに各線分のどちら側からどちら側になぞるかも探索する。

• 問題へのリンク

問題概要

座標平面上に 本の線分がある。 本目の線分は、座標 の点と座標 の点を結んでいる。

最初、原点にレーザーがある。レーザーは印字していないときは毎秒 だけ進むことができて、印字している最中は毎秒 だけ進む。

これらの線分をすべて印字するのに要する最短時間を求めよ。

制約

• 

考えたこと

次の全探索をしよう

• レーザーで印字する線分の順序： 通り
• 各線分について、どちら側の端点から印字するか： 通り

前者はたとえば next_permutation() (C++) を用いることで実装できて、後者はたとえば bit 全探索で実装できる。全体で計算量は となる。

コード

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

int main() {
    int N;
    double S, T, res = 1LL<<60, base = 0;
    cin >> N >> S >> T;
    vector<double> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        base += sqrt((A[i]-C[i]) * (A[i]-C[i]) + (B[i]-D[i]) * (B[i]-D[i])) / T;
    }

    vector<int> order(N);
    for (int i = 0; i < N; i++) order[i] = i;
    do {
        for (int bit = 0; bit < (1 << N); ++bit) {
            double dis = base;
            vector<double> sx(N), sy(N), tx(N), ty(N);
            for (int i = 0; i < N; i++) {
                int id = order[i];
                if (bit & (1 << i)) sx[i] = A[id], sy[i] = B[id], tx[i] = C[id], ty[i] = D[id];
                else sx[i] = C[id], sy[i] = D[id], tx[i] = A[id], ty[i] = B[id];
            }
            dis += sqrt(sx[0] * sx[0] + sy[0] * sy[0]) / S;
            for (int i = 0; i+1 < N; i++) {
                double dx = abs(sx[i+1] - tx[i]), dy = abs(sy[i+1] - ty[i]);
                dis += sqrt(dx * dx + dy * dy) / S;
            }
            res = min(res, dis);
        }
    } while (next_permutation(order.begin(), order.end()));
    cout << fixed << setprecision(10) << res << endl;
}