mod io { pub fn scan(r: &mut R) -> Vec { let mut res = Vec::new(); loop { let buf = match r.fill_buf() { Ok(buf) => buf, Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue, Err(e) => panic!(e), }; let (done, used, buf) = { match buf.iter().position(u8::is_ascii_whitespace) { Some(i) => (i > 0 || res.len() > 0, i + 1, &buf[..i]), None => (buf.is_empty(), buf.len(), buf), } }; res.extend_from_slice(buf); r.consume(used); if done { return res; } } } } use std::f64::consts::PI; const FRAC_PI_180: f64 = PI / 180.0; const INF: f64 = 1e9; const EPS: f64 = 1e-9; struct Sushi { x: f64, y: f64, r: f64, v: f64, a: f64, } impl Sushi { fn pos(&self, t: f64) -> (f64, f64) { let x = self.x + self.r * ((self.v * t + self.a) * FRAC_PI_180).cos(); let y = self.y + self.r * ((self.v * t + self.a) * FRAC_PI_180).sin(); (x, y) } fn time(&self, w: f64, t0: f64, (x0, y0): (f64, f64)) -> f64 { let mut left = t0; let mut right = t0 + ((self.x - x0).hypot(self.y - y0) + self.r) / w + EPS; while (left - right).abs() > EPS { let t = (left + right) * 0.5; let (x, y) = self.pos(t); if (t - t0) * w <= (x - x0).hypot(y - y0) { left = t; } else { right = t; } } left } } #[allow(unused_macros)] fn run(reader: &mut R, writer: &mut W) { macro_rules! scan { ([$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($t)).collect::>()); (($($t:tt),*)) => (($(scan!($t)),*)); ([u8]) => (io::scan(reader)); (String) => (unsafe { String::from_utf8_unchecked(scan!([u8])) }); ($t:ty) => (scan!(String).parse::<$t>().unwrap()); } macro_rules! println { ($($arg:tt)*) => (writeln!(writer, $($arg)*).ok()); } let (n, w) = scan!((usize, f64)); let sushi = { let mut sushi = Vec::with_capacity(n); for _ in 0..n { let (x, y, r, v, a) = scan!((f64, f64, f64, f64, f64)); sushi.push(Sushi { x, y, r, v, a }); } sushi }; let mut dp = vec![vec![INF; n]; 1 << n]; for i in 0..n { dp[1 << i][i] = sushi[i].time(w, 0.0, (0.0, 0.0)); } for bit in 1..(1 << n) { for i in 0..n { let t = dp[bit][i]; if bit >> i & 1 == 0 { continue; } let pos = sushi[i].pos(t); for j in 0..n { if bit >> j & 1 == 1 { continue; } let nt = &mut dp[bit | 1 << j][j]; *nt = (*nt).min(sushi[j].time(w, t, pos)); } } } println!("{}", dp.last().unwrap().iter().fold(INF, |acc, t| acc.min(*t))); } fn main() { let (stdin, stdout) = (std::io::stdin(), std::io::stdout()); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); run(&mut reader, &mut writer); }