アルゴリズムと数学 071

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bf

線形計画法ですが、2次元なので、領域が多角形になり、その周辺（というか頂点）をたどっていけばよいです。
ただ、微妙な数値誤差が嫌らしいので、分数を使っています。AtCoderではnum_rationalが使えます。Rationalは成分がisizeであることに注意しなければなりません。

// Linear Programming
#![allow(non_snake_case)]

use num_rational::Rational;


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


//////////////////// process ////////////////////

type InEquation = (Rational, Rational);

fn read_inequation() -> InEquation {
    let v: Vec<isize> = read_vec();
    (Rational::new(v[0], v[2]), Rational::new(v[1], v[2]))
}

fn read_input() -> Vec<InEquation> {
    let N: usize = read();
    let ineqs: Vec<InEquation> = (0..N).map(|_| read_inequation()).collect();
    return ineqs
}

fn determinant(ineq1: &InEquation, ineq2: &InEquation) -> Rational {
    ineq1.0 * ineq2.1 - ineq1.1 * ineq2.0
}

type Point = (Rational, Rational);

fn intersection(ineq1: &InEquation, ineq2: &InEquation) -> Option<Point> {
    let D = determinant(ineq1, ineq2);
    if D == Rational::new(0, 1) {
        None
    }
    else {
        Some(((ineq2.1 - ineq1.1) / D, (ineq1.0 - ineq2.0) / D))
    }
}

fn f(ineqs: Vec<InEquation>) -> f64 {
    let mut cur_ineq = ineqs.iter().
                        min_by_key(|ineq| (ineq.0.recip(), ineq.1.recip())).
                        unwrap();
    
    let mut pt0 = (cur_ineq.0.recip(), Rational::new(0, 1));
    let mut pts: Vec<Point> = Vec::new();
    pts.push(pt0);
    loop {
        let mut v: Vec<(Point, &InEquation)> = Vec::new();
        for ineq in ineqs.iter() {
            if let Some(pt) = intersection(ineq, &cur_ineq) {
                if Rational::new(0, 1) < pt.0 && pt.0 < pt0.0 {
                    v.push((pt, ineq))
                }
            }
        }
        
        if v.is_empty() {
            let pt = (Rational::new(0, 1), cur_ineq.1.recip());
            pts.push(pt);
            break
        }
        else {
            let a = v.into_iter().max_by_key(|(pt, _)| pt.0).unwrap();
            let pt = a.0;
            cur_ineq = a.1;
            pts.push(pt);
            pt0 = pt
        }
    }
    
    let z = pts.into_iter().map(|pt| pt.0 + pt.1).max().unwrap();
    (*z.numer() as f64) / (*z.denom() as f64)
}

fn main() {
    let ineqs = read_input();
    println!("{}", f(ineqs))
}