//#[derive_readable] #[derive(Clone, Copy, Debug, PartialEq, Eq)] struct Jinja { h: i64, pos: Pos, } #[derive(Debug, Clone)] struct Problem { n: usize, k: i64, jinjas: Vec, } fn dist_sq(p1: Pos, p2: Pos) -> i64 { let d = p2 - p1; d.norm_square() } impl Problem { fn read() -> Problem { input! { n: usize, k: i64, hs: [i64; n], ps: [(i64, i64); n], } let ps = ps .iter() .copied() .map(|(x, y)| Pos::new(x, y)) .collect::>(); let jinjas = (0..n) .map(|i| Jinja { h: hs[i], pos: ps[i], }) .collect(); Problem { n, k, jinjas } } fn solve(&self) -> Answer { let n = self.n; let k = self.k; let jinjas = { let mut t = self.jinjas.clone(); t.sort_by_key(|j| j.h); t }; let ans = jinjas .iter() .copied() .filter(|j1| { // j1 の周りに j1 より古い建物がない let exists_old = jinjas.iter().copied().any(|j2| { // j2 が j1 の近くにある j1 より古い建物 dist_sq(j1.pos, j2.pos) <= k * k && j2.h > j1.h }); !exists_old }) .count() as i64; Answer { ans } } #[allow(dead_code)] fn solve_naive(&self) -> Answer { todo!(); // let ans = 0; // Answer { ans } } } #[derive(Clone, Debug, PartialEq, Eq)] struct Answer { ans: i64, } impl Answer { fn print(&self) { println!("{}", self.ans); } } fn main() { Problem::read().solve().print(); } #[cfg(test)] mod tests { #[allow(unused_imports)] use super::*; #[allow(unused_imports)] use rand::{rngs::SmallRng, seq::SliceRandom, *}; #[test] fn test_problem() { assert_eq!(1 + 1, 2); } #[allow(dead_code)] #[derive(Debug)] struct WrongTestCase { problem: Problem, main_ans: Answer, naive_ans: Answer, } #[allow(dead_code)] fn check(p: &Problem) -> Option { let main_ans = p.solve(); let naive_ans = p.solve_naive(); if main_ans != naive_ans { Some(WrongTestCase { problem: p.clone(), main_ans, naive_ans, }) } else { None } } #[allow(dead_code)] fn make_random_problem(rng: &mut SmallRng) -> Problem { todo!() // let n = rng.gen_range(1..=10); // let p = Problem { _a: n }; // println!("{:?}", &p); // p } #[allow(unreachable_code)] #[test] fn test_with_naive() { let num_tests = 0; let max_wrong_case = 10; // この件数間違いが見つかったら打ち切り let mut rng = SmallRng::seed_from_u64(42); // let mut rng = SmallRng::from_entropy(); let mut wrong_cases: Vec = vec![]; for _ in 0..num_tests { let p = make_random_problem(&mut rng); let result = check(&p); if let Some(wrong_test_case) = result { wrong_cases.push(wrong_test_case); } if wrong_cases.len() >= max_wrong_case { break; } } if !wrong_cases.is_empty() { for t in &wrong_cases { println!("{:?}", t.problem); println!("main ans : {:?}", t.main_ans); println!("naive ans: {:?}", t.naive_ans); println!(); } println!("{} cases are wrong.", wrong_cases.len()); panic!(); } } } // ====== import ====== #[allow(unused_imports)] use proconio::{ derive_readable, fastout, input, marker::{Bytes, Chars, Usize1}, }; #[allow(unused_imports)] use std::cmp::Reverse; #[allow(unused_imports)] use std::collections::{BinaryHeap, HashMap, HashSet}; // ====== output func ====== #[allow(unused_imports)] use print_vec::*; pub mod print_vec { use proconio::fastout; #[fastout] pub fn print_vec(arr: &[T]) { for a in arr { println!("{:?}", a); } } #[fastout] pub fn print_vec_1line(arr: &[T]) { let msg = arr .iter() .map(|x| format!("{:?}", x)) .collect::>() .join(" "); println!("{}", msg); } #[fastout] pub fn print_vec2(arr: &Vec>) { for row in arr { let msg = row .iter() .map(|x| format!("{:?}", x)) .collect::>() .join(" "); println!("{}", msg); } } pub fn print_bytes(bytes: &[u8]) { let msg = String::from_utf8(bytes.to_vec()).unwrap(); println!("{}", msg); } pub fn print_chars(chars: &[char]) { let msg = chars.iter().collect::(); println!("{}", msg); } #[fastout] pub fn print_vec_bytes(vec_bytes: &[Vec]) { for row in vec_bytes { let msg = String::from_utf8(row.to_vec()).unwrap(); println!("{}", msg); } } } #[allow(unused)] fn print_yesno(ans: bool) { let msg = if ans { "Yes" } else { "No" }; println!("{}", msg); } // ====== snippet ====== use pos::*; pub mod pos { use std::ops::{Add, AddAssign, Mul, Neg, Sub, SubAssign}; #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct Pos { pub x: T, pub y: T, } impl Pos { pub fn new(x: T, y: T) -> Pos { Pos { x, y } } } impl + Copy> Pos { pub fn scala_mul(self, rhs: T) -> Pos { Pos::new(self.x * rhs, self.y * rhs) } } impl + Mul + Copy> Pos { pub fn inner_product(self, rhs: Self) -> T { self.x * rhs.x + self.y * rhs.y } pub fn norm_square(self) -> T { self.inner_product(self) } } impl + Copy> Add for Pos { type Output = Pos; fn add(self, rhs: Self) -> Self::Output { Pos::new(self.x + rhs.x, self.y + rhs.y) } } impl + Copy> Sub for Pos { type Output = Pos; fn sub(self, rhs: Self) -> Self::Output { Pos::new(self.x - rhs.x, self.y - rhs.y) } } impl> Neg for Pos { type Output = Self; fn neg(self) -> Self::Output { Pos::new(-self.x, -self.y) } } impl + Copy> AddAssign for Pos { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs } } impl + Copy> SubAssign for Pos { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs } } }