Submission #73939111

---

Source Code Expand

use proconio::input;
use std::collections::HashSet;

#[derive(Clone)]
struct Point {
    x: f64,
    y: f64,
    id: usize,
}

// 2 カラムゲームの値を計算
fn f1(u: &[f64], v: &[f64]) -> f64 {
    let n = u.len();
    if n == 0 {
        return 0.0;
    }
    
    // 純粋戦略の下限
    let mut r: f64 = 0.0;
    for i in 0..n {
        r = r.max(u[i].min(v[i]));
    }
    
    // u[i] > v[i] と u[i] < v[i] に分割
    let mut pos = Vec::new();
    let mut neg = Vec::new();
    
    for i in 0..n {
        let d = u[i] - v[i];
        if d > 1e-15 {
            pos.push(Point { x: d, y: u[i], id: i });
        } else if d < -1e-15 {
            neg.push(Point { x: -d, y: u[i], id: i });
        }
    }
    
    if pos.is_empty() || neg.is_empty() {
        return r;
    }
    
    // 凸包を構築
    let hull = |mut points: Vec<Point>| -> Vec<Point> {
        points.sort_by(|a, b| {
            a.x.partial_cmp(&b.x).unwrap()
                .then_with(|| b.y.partial_cmp(&a.y).unwrap())
        });
        let mut h: Vec<Point> = Vec::new();
        for t in points {
            while h.len() >= 2 {
                let b: &Point = &h[h.len() - 2];
                let c: &Point = &h[h.len() - 1];
                if (c.x - b.x) * (t.y - b.y) - (c.y - b.y) * (t.x - b.x) >= 0.0 {
                    h.pop();
                } else {
                    break;
                }
            }
            h.push(t);
        }
        h
    };
    
    let h1 = hull(pos);
    let h2 = hull(neg);
    
    // 凸包の交点から最適値を計算
    for p in &h1 {
        for q in &h2 {
            let z = (q.x * p.y + p.x * q.y) / (p.x + q.x);
            r = r.max(z);
        }
    }
    
    r
}

// 特定の行 s を除いた 2 カラムゲーム
fn f2(u: &[f64], v: &[f64], s: usize) -> f64 {
    let n = u.len();
    let mut a = Vec::with_capacity(n - 1);
    let mut b = Vec::with_capacity(n - 1);
    for i in 0..n {
        if i != s {
            a.push(u[i]);
            b.push(v[i]);
        }
    }
    f1(&a, &b)
}

// 行列のゲーム値を計算（列数が 1, 2, 3 の場合）
fn f3(g: &[Vec<f64>]) -> f64 {
    let r = g.len();
    if r == 0 {
        return 0.0;
    }
    let c = g[0].len();
    
    if c == 1 {
        let mut m: f64 = 1e18;
        for i in 0..r {
            m = m.min(g[i][0]);
        }
        return m;
    }
    
    if c == 2 {
        let mut ln = Vec::new();
        for i in 0..r {
            ln.push((g[i][0] - g[i][1], g[i][1]));
        }
        
        let mut cand = vec![0.0_f64, 1.0_f64];
        for i in 0..r {
            for j in (i + 1)..r {
                let d = ln[i].0 - ln[j].0;
                if d.abs() > 1e-15 {
                    let p = -(ln[i].1 - ln[j].1) / d;
                    if p >= -1e-9 && p <= 1.0 + 1e-9 {
                        cand.push(p.max(0.0).min(1.0));
                    }
                }
            }
        }
        
        let mut ans: f64 = -1e18;
        for &p in &cand {
            let mut m: f64 = 1e18;
            for i in 0..r {
                m = m.min(ln[i].0 * p + ln[i].1);
            }
            ans = ans.max(m);
        }
        return ans;
    }
    
    // c == 3
    let mut best: f64 = -1e18;
    let n = r;
    
    let mut a = vec![0.0_f64; n];
    let mut b = vec![0.0_f64; n];
    let mut c_vals = vec![0.0_f64; n];
    
    for i in 0..n {
        a[i] = g[i][0] - g[i][2];
        b[i] = g[i][1] - g[i][2];
        c_vals[i] = g[i][2];
    }
    
    let mut chk = |x: f64, y: f64| {
        if x < -1e-9 || y < -1e-9 || x + y > 1.0 + 1e-9 {
            return;
        }
        let x = x.max(0.0).min(1.0);
        let y = y.max(0.0).min(1.0 - x);
        
        let mut m: f64 = 1e18;
        for i in 0..n {
            m = m.min(a[i] * x + b[i] * y + c_vals[i]);
        }
        best = best.max(m);
    };
    
    // 3 行の交点
    for i in 0..n {
        for j in (i + 1)..n {
            for k in (j + 1)..n {
                let a1 = a[i] - a[j];
                let b1 = b[i] - b[j];
                let c1 = c_vals[j] - c_vals[i];
                let a2 = a[i] - a[k];
                let b2 = b[i] - b[k];
                let c2 = c_vals[k] - c_vals[i];
                
                let d = a1 * b2 - a2 * b1;
                if d.abs() < 1e-15 {
                    continue;
                }
                
                let x = (c1 * b2 - c2 * b1) / d;
                let y = (a1 * c2 - a2 * c1) / d;
                chk(x, y);
            }
        }
    }
    
    // 2 行の交点（境界）
    for i in 0..n {
        for j in (i + 1)..n {
            let d = b[i] - b[j];
            let e = c_vals[j] - c_vals[i];
            if d.abs() > 1e-15 {
                chk(0.0, e / d);
            }
        }
    }
    
    for i in 0..n {
        for j in (i + 1)..n {
            let d = a[i] - a[j];
            let e = c_vals[j] - c_vals[i];
            if d.abs() > 1e-15 {
                chk(e / d, 0.0);
            }
        }
    }
    
    // x + y = 1 の境界
    for i in 0..n {
        for j in (i + 1)..n {
            let d = (a[i] - b[i]) - (a[j] - b[j]);
            let e = (b[j] + c_vals[j]) - (b[i] + c_vals[i]);
            if d.abs() > 1e-15 {
                let x = e / d;
                chk(x, 1.0 - x);
            }
        }
    }
    
    // 頂点
    chk(0.0, 0.0);
    chk(1.0, 0.0);
    chk(0.0, 1.0);
    
    best
}

fn solve() {
    input! {
        n: usize,
    }
    
    let mut p = vec![[0.0_f64; 3]; n];
    for i in 0..n {
        input! {
            x0: i64, x1: i64, x2: i64
        }
        p[i] = [
            x0 as f64 / 1_000_000.0,
            x1 as f64 / 1_000_000.0,
            x2 as f64 / 1_000_000.0,
        ];
    }
    
    let col = [[1, 2], [0, 2], [0, 1]];
    
    let mut vs = [0.0_f64; 3];
    let mut id1 = [0usize; 3];
    let mut id2 = [0usize; 3];
    let mut rm1 = [0.0_f64; 3];
    let mut rm2 = [0.0_f64; 3];
    
    for b in 0..3 {
        let c0 = col[b][0];
        let c1 = col[b][1];
        
        let mut a = vec![0.0_f64; n];
        let mut bb = vec![0.0_f64; n];
        for i in 0..n {
            a[i] = p[i][c0];
            bb[i] = p[i][c1];
        }
        
        vs[b] = f1(&a, &bb);
        
        // 最適な行を特定
        let mut best: f64 = 0.0;
        let mut id = 0;
        for i in 0..n {
            let val = a[i].min(bb[i]);
            if val > best {
                best = val;
                id = i;
            }
        }
        
        let mut pos = Vec::new();
        let mut neg = Vec::new();
        for i in 0..n {
            let d = a[i] - bb[i];
            if d > 1e-15 {
                pos.push(Point { x: d, y: a[i], id: i });
            } else if d < -1e-15 {
                neg.push(Point { x: -d, y: a[i], id: i });
            }
        }
        
        let mut mi: isize = -1;
        let mut mj: isize = -1;
        let mut mv: f64 = best;
        
        if !pos.is_empty() && !neg.is_empty() {
            let hull = |mut points: Vec<Point>| -> Vec<Point> {
                points.sort_by(|a, b| {
                    a.x.partial_cmp(&b.x).unwrap()
                        .then_with(|| b.y.partial_cmp(&a.y).unwrap())
                });
                let mut h: Vec<Point> = Vec::new();
                for t in points {
                    while h.len() >= 2 {
                        let q: &Point = &h[h.len() - 2];
                        let r: &Point = &h[h.len() - 1];
                        if (r.x - q.x) * (t.y - q.y) - (r.y - q.y) * (t.x - q.x) >= 0.0 {
                            h.pop();
                        } else {
                            break;
                        }
                    }
                    h.push(t);
                }
                h
            };
            
            let h1 = hull(pos);
            let h2 = hull(neg);
            
            for pp in &h1 {
                for qq in &h2 {
                    let v = (qq.x * pp.y + pp.x * qq.y) / (pp.x + qq.x);
                    if v > mv + 1e-12 {
                        mv = v;
                        mi = pp.id as isize;
                        mj = qq.id as isize;
                    }
                }
            }
        }
        
        vs[b] = mv;
        
        if mi >= 0 {
            id1[b] = mi as usize;
            id2[b] = mj as usize;
        } else {
            id1[b] = id;
            id2[b] = id;
        }
        
        rm1[b] = f2(&a, &bb, id1[b]);
        
        if id1[b] != id2[b] {
            rm2[b] = f2(&a, &bb, id2[b]);
        } else {
            rm2[b] = rm1[b];
        }
    }
    
    // 候補行の集合
    let mut s: HashSet<usize> = HashSet::new();
    for b in 0..3 {
        s.insert(id1[b]);
        s.insert(id2[b]);
    }
    
    // 行列を構築
    let mut mat = Vec::new();
    
    {
        let mut r = vec![0.0_f64; 3];
        for b in 0..3 {
            r[b] = vs[b];
        }
        mat.push(r);
    }
    
    for &x in &s {
        let mut r = vec![0.0_f64; 3];
        for b in 0..3 {
            if x == id1[b] {
                r[b] = rm1[b];
            } else if x == id2[b] {
                r[b] = rm2[b];
            } else {
                r[b] = vs[b];
            }
        }
        mat.push(r);
    }
    
    let ans = f3(&mat);
    println!("{}", ans);
}

fn main() {
    input! {
        t: usize,
    }
    for _ in 0..t {
        solve();
    }
}

Submission Info

Judge Result