use std::collections::BTreeMap; use proconio::input; fn main() { input! { (n, k): (usize, usize), hh: [usize; n], xy: [(usize, usize); n], } let square_k = k.pow(2); let mut coords_per_history: BTreeMap> = BTreeMap::new(); for (&h, &coord) in hh.iter().zip(&xy) { coords_per_history.entry(h).or_default().push(coord); } let mut num_removed_shrines = 0_usize; let mut candidate_coords: Vec<(usize, usize)> = vec![]; for coords in coords_per_history.into_values() { let check_removable = |low_coord: (usize, usize)| { coords .iter() .any(|&high_coord| calc_square_dist(low_coord, high_coord) <= square_k) }; let prev_num_candidates = candidate_coords.len(); candidate_coords.retain(|&low_coord| !check_removable(low_coord)); num_removed_shrines += prev_num_candidates - candidate_coords.len(); candidate_coords.extend(coords); } println!("{}", n - num_removed_shrines); } fn calc_square_dist(coord1: (usize, usize), coord2: (usize, usize)) -> usize { let (x1, y1) = coord1; let (x2, y2) = coord2; x1.abs_diff(x2).pow(2) + y1.abs_diff(y2).pow(2) }