https://atcoder.jp/contests/abc374/tasks/abc374_d?lang=ja
単なるしらみつぶしですね。
// Laser Marking #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } fn permutations<T: Copy>(a: &Vec<T>) -> Vec<Vec<T>> { let N = a.len(); if N == 1 { vec![a.to_vec()] } else { let mut bs: Vec<Vec<T>> = vec![]; for i in 0..N { let v: Vec<T> = (0..N).filter(|&j| j != i). map(|j| a[j]).collect(); let bs_sub = permutations(&v); for mut b in bs_sub.into_iter() { b.insert(0, a[i]); bs.push(b) } } bs } } //////////////////// Segment //////////////////// type Point = (f64, f64); type Segment = (f64, f64, f64, f64); fn read_seg() -> Segment { let v: Vec<f64> = read_vec(); (v[0], v[1], v[2], v[3]) } //////////////////// process //////////////////// fn read_input() -> (f64, f64, Vec<Segment>) { let v: Vec<f64> = read_vec(); let (N, S, T) = (v[0] as usize, v[1], v[2]); let segments: Vec<Segment> = (0..N).map(|_| read_seg()).collect(); (S, T, segments) } fn collect_points(segments: &Vec<Segment>) -> Vec<Point> { let mut points: Vec<Point> = vec![(0.0, 0.0)]; for &(v1, v2, v3, v4) in segments.iter() { points.push((v1, v2)); points.push((v3, v4)) } points } fn calc_points_dist((x1, y1): Point, (x2, y2): Point) -> f64 { ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)).sqrt() } fn calc_points_time(points: Vec<Point>, S: f64, T: f64) -> f64 { let mut t = 0.0; for i in 0..points.len()-1 { let v = if (i & 1) == 0 { S } else { T }; t += calc_points_dist(points[i], points[i+1]) / v } t } fn calc_time(segments: Vec<Segment>, S: f64, T: f64) -> f64 { let points = collect_points(&segments); calc_points_time(points, S, T) } fn inverse_segment(seg: Segment) -> Segment { (seg.2, seg.3, seg.0, seg.1) } fn inverse(i: usize, segments: &Vec<Segment>) -> Vec<Segment> { let N = segments.len(); let mut new_segs: Vec<Segment> = vec![]; for k in 0..N { if ((i >> k) & 1) == 0 { new_segs.push(segments[k]) } else { new_segs.push(inverse_segment(segments[k])) } } new_segs } fn F(S: f64, T: f64, segments: Vec<Segment>) -> f64 { let N = segments.len(); let mut t_min = f64::MAX; for segs in permutations(&segments) { for i in 0..(1<<N) { let t = calc_time(inverse(i, &segs), S, T); if t < t_min { t_min = t } } } t_min } fn main() { let (S, T, segments) = read_input(); println!("{}", F(S, T, segments)) }