#[allow(unused_imports)] use std::{collections::{HashSet, HashMap, BTreeSet, BTreeMap, BinaryHeap, VecDeque}, cmp::{Reverse, max, min}, mem::swap}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8からお借りしました 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)] struct KDNode{ point: Vec, 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>, d: usize)->Option{ if points.is_empty(){return None;} let k = points[0].len(); let axis = d%k; let sort = points; sort.sort_by(|a, b| a[axis].cmp(&b[axis])); 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: &Vec, i: Option, d: usize, res: &mut (Vec, f64)){ if let Some(idx) = i{ let node = self.tree[idx].point.clone(); let k = t.len(); let axis = d%k; let dist = dist_calc(&node, t); if dist < res.1{ *res = (node.clone(), dist); } let (nex, other) = if t[axis] < node[axis]{ 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[axis]-t[axis]).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: &Vec, q: &Vec)->f64{ p.iter().zip(q.iter()).map(|(&a, &b)| (a as f64-b as f64)*(a as f64-b as f64)).sum::().sqrt() } fn main() { input!{ n: usize, m: usize, k: usize, p: [i64; 2], v: f64, e: [(usize1, usize1); m], s: [[i64; 2]; n], t: [[i64; 2]; k], } 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 = (Vec::new(), 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![0.; n]; let mut ans = 0.; for i in 0..k{ let mut st = (Vec::new(), 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); }