Submission #58907201

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
using VVI = vector<VI>;
using VVL = vector<VL>;

int main()
{
    int n;
    double s, t;
    cin >> n >> s >> t;
    vector<double> a(n), b(n), c(n), d(n);
    REP(i,n) cin >> a[i] >> b[i] >> c[i] >> d[i];

    VI perm(n);
    REP(i,n) perm[i] = i;
    double ans = 1e18;
    do {
        REP(msak,1<<n){
            double dist = 0;
            double x = 0, y = 0;
            REP(i,n){
                int j = perm[i];
                if (msak >> j & 1){
                    dist += sqrt((a[j]-x)*(a[j]-x) + (b[j]-y)*(b[j]-y)) / s;
                    dist += sqrt((c[j]-a[j])*(c[j]-a[j]) + (d[j]-b[j])*(d[j]-b[j])) / t;
                    x = c[j];
                    y = d[j];
                } else {
                    dist += sqrt((c[j]-x)*(c[j]-x) + (d[j]-y)*(d[j]-y)) / s;
                    dist += sqrt((a[j]-c[j])*(a[j]-c[j]) + (b[j]-d[j])*(b[j]-d[j])) / t;
                    x = a[j];
                    y = b[j];
                }
            }
            chmin(ans, dist);
        }
    } while (next_permutation(perm.begin(), perm.end()));
    printf("%.10f\n", ans);
}

Submission Info

Judge Result