#[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() } } const INF: i64 = 1<<60; #[derive(Debug, Copy, Clone)] struct KDNode{ point: (i64, i64), left: Option, right: Option, axis: usize, mi1: i64, mx1: i64, mi2: i64, mx2: i64, } 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 (mut mi1, mut mx1, mut mi2, mut mx2) = (INF, -INF, INF, -INF); for i in 0..points.len(){ mi1 = mi1.min(points[i].0); mx1 = mx1.max(points[i].0); mi2 = mi2.min(points[i].1); mx2 = mx2.max(points[i].1); } let sort = points; let axis = if mx1-mi1 >= mx2-mi2{0} else {1}; 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, axis, mi1, mx1, mi2, mx2 }); 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, res: &mut ((i64, i64), f64)){ if let Some(idx) = i{ let node = self.tree[idx].point.clone(); let axis = self.tree[idx].axis; let dist = dist_calc(&node, t); if dist < res.1{ *res = (node.clone(), dist); } let (nex, other) = if (axis==0&&t.0 < node.0)||(axis==1&&t.1 < node.1){ (self.tree[idx].left, self.tree[idx].right) } else { (self.tree[idx].right, self.tree[idx].left) }; if let Some(n_idx) = nex{ self.query(t, Some(n_idx), res); } if let Some(nex) = other{ let (mix, mxx, miy, mxy) = (self.tree[nex].mi1, self.tree[nex].mx1, self.tree[nex].mi2, self.tree[nex].mx2); let ad = (possible_dist(t.0, t.1, mix, mxx, miy, mxy) as f64).sqrt(); if ad < res.1{ self.query(t, Some(nex), res); } } } } } fn possible_dist(p: i64, q: i64, mix: i64, mxx: i64, miy: i64, mxy: i64)->i64{ let (mix, mxx, miy, mxy) = (mix, mxx, miy, mxy); let f1 = mix <= p && p <= mxx; let f2 = miy <= q && q <= mxy; if f1 && f2{ return 0; } else if f1{ return (miy-q).abs().min((q-mxy).abs()).pow(2) } else if f2{ return (mix-p).abs().min((mxx-p).abs()).pow(2) } let x = (mix-p).abs().min((p-mxx).abs()); let y = (miy-q).abs().min((mxy-q).abs()); return x*x+y*y } 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 dijkstra(n: usize, v: f64, p: usize, edge: &Vec>, s: &Vec<(i64, i64)>)->Vec{ let mut time = vec![1e60; n]; time[p] = 0.; let mut used = vec![false; n]; let mut heap = BinaryHeap::new(); heap.push(Reverse((OrderedFloat(0.), p))); while let Some(Reverse((OrderedFloat(w), x))) = heap.pop(){ if used[x]{continue} used[x] = true; time[x] = w; for &nex in &edge[x]{ if used[nex]{continue} let dx = dist_calc(&s[nex], &s[x])/v; if time[nex] > w+dx{ heap.push(Reverse((OrderedFloat(w+dx), nex))); } } } time } 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 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 mix, mut mxx, mut miy, mut mxy) = (INF, -INF, INF, -INF); for &(u, v) in &s{ mix = mix.min(u); mxx = mxx.max(u); miy = miy.min(v); mxy = mxy.max(v); } let mut ans = 0.; let mut kdtree = KDTree::new(); kdtree.build(&mut s, 0); let mut hotel = ((0, 0), 1e18); kdtree.query(&p, Some(0), &mut hotel); let ss = dic[&hotel.0]; let pre = dist_calc(&p, &s[ss]); let time = dijkstra(n, v, ss, &edge, &s); for i in 0..k{ let mut res = ((0, 0), 1e18); kdtree.query(&t[i], Some(0), &mut res); let d1 = dist_calc(&t[i], &res.0); let sub = time[dic[&res.0]]; ans += (dist_calc(&p, &t[i]).min(d1+sub+pre))*2.; } println!("{}", ans); }