結果

問題 No.1413 Dynamic Sushi
ユーザー merom686
提出日時 2021-02-28 22:39:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 403 ms / 4,000 ms
コード長 2,084 bytes
コンパイル時間 1,625 ms
コンパイル使用メモリ 92,592 KB
最終ジャッジ日時 2025-01-19 08:47:43
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

template <class T>
void chmin(T &a, T b) {
    if (b < a) a = b;
}

constexpr double INF = 1e+9;
constexpr int N = 12;
double dp[1 << N][N];

struct P {
    int x, y, r;
    double v, a;
};

int main() {
    int n, w;
    cin >> n >> w;

    P p[N];
    for (int i = 0; i < n; i++) {
        int x, y, r, v, a;
        cin >> x >> y >> r >> v >> a;

        double t = acos(-1) / 180;
        p[i] = { x, y, r, v * t, a * t };
    }

    auto f = [&](int i, double t) {
        double z = p[i].v * t + p[i].a;
        return pair<double, double>(p[i].x + p[i].r * cos(z), p[i].y + p[i].r * sin(z));
    };

    auto r2 = [](double x, double y) {
        return x * x + y * y;
    };

    auto g = [&](double x, double y, double t, int i) {
        double t0 = 0, t1 = (hypot(x - p[i].x, y - p[i].y) + p[i].r) / w, t2;
        while (t1 - t0 > 1e-8 * max(1.0, t0)) {
            t2 = (t0 + t1) * 0.5;
            auto [x1, y1] = f(i, t + t2);
            (r2(x - x1, y - y1) > r2(t2 * w, 0) ? t0 : t1) = t2;
        }
        return t + (t0 + t1) * 0.5;
    };

    for (int k = 0; k < 1 << n; k++) {
        for (int i = 0; i < n; i++) {
            dp[k][i] = INF;
        }
    }
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = g(0, 0, 0, i);
    }

    for (int k = 0; k < 1 << n; k++) {
        for (int i = 0; i < n; i++) {
            if (k & 1 << i) {
                double s = dp[k][i];
                int l = k ^ 1 << i;
                for (int j = 0; j < n; j++) {
                    if (l & 1 << j) {
                        double t = dp[l][j];
                        auto [x, y] = f(j, t);
                        chmin(s, g(x, y, t, i));
                    }
                }
                dp[k][i] = s;
            }
        }
    }

    double r = INF;
    for (int i = 0; i < n; i++) {
        chmin(r, dp[(1 << n) - 1][i]);
    }
    printf("%.12f\n", r);

    return 0;
}
0