#[allow(unused_imports)] use std::{ cell::RefCell, convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,}, fs::{File}, hash::{Hash, Hasher}, iter::{Product, Sum}, marker::PhantomData, ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, }, str::FromStr, sync::{atomic::{self, AtomicU32, AtomicU64}, Once}, collections::{*}, mem::{swap}, cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd}, thread::LocalKey, f64::consts::PI, time::Instant, io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write}, }; #[allow(unused_imports)] use proconio::{input, input_interactive, marker::{*}}; #[allow(unused_imports)] //use rand::{thread_rng, Rng, seq::SliceRandom}; #[allow(unused_imports)] //use ac_library::{*}; #[allow(dead_code)] const INF: i64 = 1<<60; #[allow(dead_code)] const MOD: i64 = 998244353; #[allow(dead_code)] const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)]; pub fn closest_pair(ps: &mut Vec<(f64, f64)>)->f64{ ps.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap().then(a.1.partial_cmp(&b.1).unwrap())); closest_find(ps) } fn closest_find(ps: &mut [(f64, f64)])->f64{ if ps.len()<=1{ return 1e60; } let m = ps.len()/2; let center = ps[m].0; let mut res = closest_find(&mut ps[..m]); res = res.min(closest_find(&mut ps[m..])); let (mut idx1, mut idx2) = (0, 0); let mut nps = Vec::with_capacity(ps.len()); while idx1 < m || idx2+m < ps.len(){ if idx1 = Vec::new(); for &(x, y) in ps.iter(){ if (x-center).abs() > res{continue} for &(px, py) in near.iter().rev(){ if res+py < y{break;} let (dx, dy) = ((x-px).abs(), y-py); res = res.min((dx*dx+dy*dy).sqrt()); } near.push((x, y)); } res } //use proconio::fastout; //#[fastout] fn main(){ input!{ n: usize, mut p: [(f64, f64); n], mut q: [(f64, f64); n], } let d1 = closest_find(&mut p); let d2 = closest_find(&mut q); println!("{}", d2/d1); }