#[allow(unused_imports)] use std::{collections::{HashSet, HashMap, BTreeSet, BTreeMap, BinaryHeap, VecDeque}, cmp::{Reverse, PartialOrd, Ordering, max, min}, mem::swap}; macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } #[derive(Debug, PartialEq, PartialOrd)] struct OrderedFloat(f64); impl Eq for OrderedFloat {} impl Ord for OrderedFloat { fn cmp(&self, other: &Self) -> Ordering{ self.partial_cmp(&other).unwrap() } } #[derive(Debug)] struct KDNode{ point: (i64, i64), left: Option, right: Option, } pub struct KDTree{ tree: Vec, } impl KDTree { pub fn new() -> Self{ KDTree {tree: Vec::new()} } pub fn build(&mut self, points: &mut Vec<(i64, i64)>, d: usize)->Option{ if points.is_empty(){return None;} let k = 2; let axis = d%k; let sort = points; if axis==0{ sort.sort_by(|a, b| a.0.cmp(&b.0)); } else { sort.sort_by(|a, b| a.1.cmp(&b.1)); } let m =sort.len()/2; let mp = sort[m].clone(); let ind = self.tree.len(); self.tree.push(KDNode{ point: mp, left: None, right: None }); let left = self.build(&mut sort[..m].to_vec(), d+1); self.tree[ind].left = left; let right = self.build(&mut sort[m+1..].to_vec(), d+1); self.tree[ind].right = right; Some(ind) } pub fn query(&mut self, t: &(i64, i64), i: Option, d: usize, res: &mut ((i64, i64), f64)){ if let Some(idx) = i{ let node = self.tree[idx].point.clone(); let k = 2; let axis = d%k; let dist = dist_calc(&node, t); if dist < res.1{ *res = (node.clone(), dist); } if axis==0{ let (nex, other) = if t.0 < node.0{ let p = self.tree[idx].left; let q = self.tree[idx].right; (p, q) } else { let p = self.tree[idx].right; let q = self.tree[idx].left; (p, q) }; self.query(t, nex, d+1, res); let di = (node.0-t.0).abs(); if (di as f64) < res.1{ if let Some(n_idx) = other{ self.query(t, Some(n_idx), d+1, res); } } } else { let (nex, other) = if t.1 < node.1{ let p = self.tree[idx].left; let q = self.tree[idx].right; (p, q) } else { let p = self.tree[idx].right; let q = self.tree[idx].left; (p, q) }; self.query(t, nex, d+1, res); let di = (node.1-t.1).abs(); if (di as f64) < res.1{ if let Some(n_idx) = other{ self.query(t, Some(n_idx), d+1, res); } } } } } } fn dist_calc(p: &(i64, i64), q: &(i64, i64))->f64{ let (x1, y1) = p; let (x2, y2) = q; (((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) as f64).sqrt() } fn main() { input!{ n: usize, m: usize, k: usize, p: (i64, i64), s: [(i64, i64); n], t: [(i64, i64); k], v: f64, e: [(usize1, usize1); m], } let p = (p.0, p.1); let mut s = s.clone(); let mut edge = vec![Vec::new(); n]; for &(u, v) in &e{ edge[u].push(v); edge[v].push(u); } let mut dic = HashMap::new(); for i in 0..n{ dic.insert((s[i].0, s[i].1), i); } let mut kdtree = KDTree::new(); kdtree.build(&mut s, 0); let mut hotel = ((0, 0), 1e18); kdtree.query(&p, Some(0), 0, &mut hotel); let ss = dic[&(hotel.0.0, hotel.0.1)]; let pre = hotel.1; let mut time = vec![1e60; n]; time[ss] = 0.; let mut used = vec![false; n]; let mut heap = BinaryHeap::new(); heap.push(Reverse((OrderedFloat(0.), ss))); while let Some(Reverse((OrderedFloat(w), x))) = heap.pop(){ if used[x]{continue} used[x] = true; for &nex in &edge[x]{ if used[nex]{continue} let dx = dist_calc(&s[nex], &s[x])/v; if time[nex] > w+dx{ time[nex] = time[x]+dx; heap.push(Reverse((OrderedFloat(time[nex]), nex))); } } } let mut ans = 0.; for i in 0..k{ let mut st = ((0, 0), 1e18); kdtree.query(&t[i], Some(0), 0, &mut st); let d1 = dist_calc(&st.0, &t[i]); let t1 = time[dic[&(st.0.0, st.0.1)]]; ans += (dist_calc(&p, &t[i]).min(pre+d1+t1))*2.; } println!("{}", ans); }