fn main() { ioset! { inp, buf } macro_rules! scan { ($($r:tt)*) => { input! { inp, $($r)* } } } macro_rules! print { ($($t:expr),*) => { write!(buf, $($t),*).unwrap(); } } scan! { C: f64, D: f64, } let mut xrsh = Xorshift::new(); let ans = seidel_lp(&mut xrsh, 2, &[1.0, 2.0], &[(vec![3.0 / 4.0, 2.0 / 7.0], C), (vec![1.0 / 4.0, 5.0 / 7.0], D), (vec![-1.0, 0.0], 0.0), (vec![0.0, -1.0], 0.0)], &[(0.0, 2000.0), (0.0, 2000.0)]).unwrap(); print!("{:.10}\n", ans[0] * 1000.0 + ans[1] * 2000.0); } pub trait ToVec { type Item; fn tovec(self) -> Vec; } impl ToVec for I { type Item = ::Item; fn tovec(self) -> Vec { self.collect::>() } } #[derive(Debug)] #[allow(dead_code)] pub struct Xorshift { seed: u64, } impl Xorshift { #[allow(dead_code)] pub fn new() -> Xorshift { Xorshift { seed: 0xf0fb588ca2196dac, } } #[allow(dead_code)] pub fn with_seed(seed: u64) -> Xorshift { Xorshift { seed } } #[inline] #[allow(dead_code)] pub fn next(&mut self) -> u64 { self.seed = self.seed ^ (self.seed << 13); self.seed = self.seed ^ (self.seed >> 7); self.seed = self.seed ^ (self.seed << 17); self.seed } #[inline] #[allow(dead_code)] pub fn rand(&mut self, m: u64) -> u64 { self.next() % m } #[inline] #[allow(dead_code)] // 0.0 ~ 1.0 pub fn randf(&mut self) -> f64 { use std::mem; const UPPER_MASK: u64 = 0x3FF0000000000000; const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF; let tmp = UPPER_MASK | (self.next() & LOWER_MASK); let result: f64 = unsafe { mem::transmute(tmp) }; result - 1.0 } } pub fn seidel_lp(xrsh: &mut Xorshift, d: usize, c: &[f64], mat: &[(Vec, f64)], bounds: &[(f64, f64)]) -> Option> { match d { 0 => unreachable!("0 dimension"), 1 => { assert!(c.len() == 1, "length of c must be 1 at this point"); let (low, high) = bounds[0]; let (h, l, z) = mat .iter() .fold((high, low, 0f64), |(h, l, z), (a, p)| { assert!(a.len() == 1, "length of a must be 1 at this point"); match a[0].partial_cmp(&0f64) { None => unreachable!("a[0] is Nan?"), Some(Ordering::Greater) => { let nh = if p / a[0] <= h { p / a[0] } else { h }; (nh, l, z) } Some(Ordering::Less) => { let nl = if p / a[0] >= l { p / a[0] } else { l }; (h, nl, z) } Some(Ordering::Equal) => { let nz = if *p <= z { *p } else { z }; (h, l, nz) } } }); if z < 0f64 || h < l { None } else if c[0] >= 0f64 { Some(vec![h]) } else { Some(vec![l]) } } d if mat.is_empty() => { Some((0..d).map(|i| if c[i] >= 0f64 { bounds[i].1 } else { bounds[i].0 }).collect()) } d => { let rmi = (xrsh.next() as usize) % mat.len(); let (a, ap) = mat[rmi].clone(); let next_mat = (0..mat.len()).filter(|i| *i != rmi).map(|i| mat[i].clone()).collect::>(); let v = if let Some(v) = seidel_lp(xrsh, d, c, &next_mat, bounds) { v } else { return None }; let value: f64 = (0..d) .map(|i| a[i] * v[i]) .sum(); if value <= ap { Some(v) } else { let k = if let Some(k) = (0..d).rev().find(|i| a[*i] != 0f64) { k } else { return None }; let next_bounds = (0..d).filter(|i| *i != k).map(|i| bounds[i].clone()).collect::>(); let mut bar_mat = next_mat.iter().map(|(b, bp)| { let ratio = b[k] / a[k]; let v = (0..d) .filter(|i| *i != k) .map(|i| { b[i] - ratio * a[i] }) .collect::>(); (v, bp - ratio * ap) }).collect::>(); let bar_c = (0..d) .filter(|i| *i != k) .map(|i| { c[i] - (c[k] / a[k]) * a[i] }).collect::>(); let f = (0..d).filter(|i| *i != k).map(|i| { - (1f64 / a[k]) * a[i] }).collect::>(); let fp = bounds[k].1; let g = (0..d).filter(|i| *i != k).map(|i| { - (1f64 / a[k]) * a[i] }).collect::>(); let gp = bounds[k].0; bar_mat.push((f, fp)); bar_mat.push((g, gp)); if let Some(mut v) = seidel_lp(xrsh, d - 1, &bar_c, &bar_mat, &next_bounds) { v.insert(k, 0f64); let s: f64 = (0..d) .map(|i| a[i] * v[i]) .sum(); v[k] = (ap - s) / a[k]; Some(v) } else { None } } } } } /* I/O */ use std::io::{ stdout, BufWriter, Write }; #[macro_export] macro_rules! ioset { ($inp:ident, $buf:ident) => { inset!($inp); outset!($buf); } } #[macro_export] macro_rules! inset { (source = $s:expr, $iter:ident) => { let mut $iter = $s.split_whitespace(); }; ($iter:ident) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut $iter = s.split_whitespace(); } } #[macro_export] macro_rules! input { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt, $($r:tt)*) => { let $var = read_value!($iter, $t); input! { $iter, $($r)* } }; ($iter:expr, mut $var:ident : $t:tt, $($r:tt)*) => { let mut $var = read_value!($iter, $t); input! { $iter, $($r)* } }; ($iter:expr, ($var:expr) : $t:tt, $($r:tt)*) => { $var = read_value!($iter, $t); input! { $iter, $($r)* } }; } #[macro_export] macro_rules! read_value { // tuple ($iter:expr, ( $($t:tt), * )) => { ( $(read_value!($iter, $t)), * ) }; // array ($iter:expr, [ $t:tt; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; // string ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; // any other ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } #[macro_export] macro_rules! outset { ($buf:ident) => { let sout = stdout(); let mut $buf = BufWriter::new(sout.lock()); } } #[macro_export] macro_rules! output { ($buf:expr, $($t:expr),*) => { write!($buf, $($t),*).unwrap(); } } struct Chars<'a>(&'a Vec); impl<'a> std::fmt::Display for Chars<'a> { fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> { write!(f, "{}", self.0.iter().collect::()) } } use std::cmp::Ordering; pub trait BinarySearch { fn lower_bound(&self, x: &T) -> usize; fn upper_bound(&self, x: &T) -> usize; } impl BinarySearch for [T] { fn lower_bound(&self, x: &T) -> usize { let mut ng = -1i64; let mut ok = self.len() as i64; while ok - ng > 1 { let m = (ok + ng) / 2; match self[m as usize].cmp(x) { Ordering::Greater | Ordering::Equal => { ok = m; } _ => { ng = m; } } } ok as usize } fn upper_bound(&self, x: &T) -> usize { let mut ng = -1i64; let mut ok = self.len() as i64; while ok - ng > 1 { let m = (ok + ng) / 2; match self[m as usize].cmp(x) { Ordering::Greater => { ok = m; } _ => { ng = m; } } } ok as usize } }