meta hacker cup 2022, round 1, lemonade life

lemonade_life.rs

// https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/C

fn bad(i: usize, j: usize, k: usize, t: &Vec<Vec<i64>>) -> bool {
    let rise1 = t[j][1] - t[i][1];
    let rise2 = t[k][1] - t[i][1];
    let run1 = t[j][0] - t[i][0];
    let run2 = t[k][0] - t[i][0];
    if run1 == 0 {
        return false;
    }
    // remove j if j is bad.
    // j bad if steeper from i to k than it is from i to j
    // gradient from i to k is higher than gradient from i to j
    run1*rise2 >= rise1*run2
}

fn bad2(i: usize, j: usize, k: usize, t: &Vec<Vec<i64>>) -> bool {
    let rise1 = t[j][1] - t[i][1];
    let rise2 = t[k][1] - t[i][1];
    let run1 = t[j][0] - t[i][0];
    let run2 = t[k][0] - t[i][0];
    if run1 == 0 {
        return false;
    }
    run1*rise2 <= rise1*run2
}

fn get_hull(mut points: Vec<Vec<i64>>) -> Vec<Vec<i64>> {
    let mut stack = vec![];
    points.sort();
    stack.push(0);
    let n = points.len();
    if n > 1 {
        stack.push(1);
    }
    for i in 2..n {
        while stack.len() >= 2 && bad(stack[stack.len()-2], stack[stack.len()-1], i, &points) {
            stack.pop();
        }
        stack.push(i);
    }
    let mut hull = vec![];
    for i in 0..stack.len()-1 {
        hull.push(points[stack[i]].clone());
    }
    stack.drain(1..);
    points.sort_by_key(|x| (x[0], -x[1]));
    if n > 1 {
        stack.push(1);
    }
    for i in 2..n {
        while stack.len() >= 2 && bad2(stack[stack.len()-2], stack[stack.len()-1], i, &points) {
            stack.pop();
        }
        stack.push(i);
    }
    for i in 1..stack.len() {
        hull.push(points[stack[i]].clone());
    }
    hull
}

fn dist(p: &Vec<Vec<i64>>, i: usize, j: usize) -> i64 {
    return (p[i][0] - p[j][0]).pow(2) + (p[i][1] - p[j][1]).pow(2)
}

fn f(hull: &Vec<Vec<i64>>, k: i64, d: i64) -> i64 {
    let n = hull.len();
    let mut dp = vec![None; n];
    let mut done = vec![false; n];
    dp[0] = Some(0i64);
    let mut i = 0;
    loop {
        if i + 1 == dp.len() {
            return dp[i].unwrap();
        }
        for j in 0..n {
            if j != i && !done[j] {
                let d_squared =  dist(&hull, i, j);
                if d_squared <= d.pow(2) {
                    let cost = d_squared.max(k) + dp[i].unwrap();
                    if dp[j].is_some() {
                        dp[j] = dp[j].min(Some(cost));
                    } else {
                        dp[j] = Some(cost);
                    }
                }
            }
        }
        done[i] = true;
        let mn = done.iter()
            .enumerate()
            .filter_map(|(i, &ok)| if !ok { dp[i].map(|d| (d, i)) } else {None})
            .min();
        if mn.is_none() {
            return -1;
        }
        i = mn.unwrap().1;
    }
}

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let t: usize = sc.read();
    for case_num in 1..=t {
        let n: usize = sc.read();
        eprintln!("case {}, n {}", case_num, n);
        let k: i64 = sc.read();
        let d: i64 = sc.read();
        let mut points = vec![];
        for _ in 0..n {
            let x: i64 = sc.read();
            let y: i64 = sc.read();
            points.push(vec![x, y]);
        }
        let hull = get_hull(points);
        eprintln!("hull size {}", hull.len());
        let ans = f(&hull, k, d); // dijkstra
        sc.write(
            format!("Case #{}: {}", case_num, ans)
        );
        sc.write("\n");
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }

    pub fn binary_vec(&mut self) -> Vec<u8> {
        self.read::<String>()
            .bytes()
            .map(|b| b - b'0')
            .collect()
    }

    pub fn grid<T, F>(&mut self, r: usize, f: &F) -> Vec<Vec<T>>
        where F: Fn(char) -> T {
        let mut g = Vec::with_capacity(r);
        for _ in 0..r {
            g.push(
                self.chars().into_iter().map(f).collect()
            )
        }
        g
    }
}