結果

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

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

using C=complex<double>;


int N;
double W;
double A[13][5];

C f(int i,double t){ return C(A[i][0],A[i][1]) + polar<double>(A[i][2],A[i][3]*t+A[i][4]); }

double T(int u,int v,double t){
  C pos=f(u,t);
  double l=0.0, r=1000.0;
  while(r-l>1.0e-8){
    double m=(l+r)/2;
    C pos_to=f(v,t+m);
    ((abs(pos_to-pos)<(m*W))?r:l) = m;
  }
  //printf("T(%d,%d,%.5f) = %.5f\n",u,v,t,t+r);
  return t+r;
}

int main(){
  cin>>N>>W;
  rep(i,N) rep(j,5) cin>>A[i][j];
  rep(i,N){ A[i][3] *= acos(-1.0)/180.0; A[i][4] *= acos(-1.0)/180.0; }
  rep(i,5) A[N][i]=0.0;
  double dp[1<<12][12]; rep(i,1<<N) rep(j,N) dp[i][j]=1.0e50;
  rep(i,N) dp[1<<i][i]=T(N,i,0.0);
  rep(F,1<<N) rep(i,N) rep(j,N){
    if(!(F&(1<<i))) continue;
    if(F&(1<<j)) continue;
    dp[F|(1<<j)][j] = min(dp[F|(1<<j)][j],T(i,j,dp[F][i]));
  }
  double ans=1.0e50; rep(i,N) ans=min(ans,dp[(1<<N)-1][i]);
  cout<<setprecision(6)<<fixed<<ans<<endl;
  return 0;
}
0