AtCoder Beginner Contest 374 D

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))
}