// -*- coding:utf-8-unix -*- // #![feature(map_first_last)] #![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] // use core::num; use std::cmp::*; use std::fmt::*; use std::hash::*; use std::iter::FromIterator; use std::*; use std::{cmp, collections, fmt, io, iter, ops, str}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const LINF: i64 = 2147483647; const INF128: i128 = 1223372036854775807000000000000; const MOD1: i64 = 1000000007; const MOD9: i64 = 998244353; const MOD: i64 = MOD9; // const MOD: i64 = MOD2; const UMOD: usize = MOD as usize; const M_PI: f64 = 3.14159265358979323846; // use proconio::input; // const MOD: i64 = INF; use cmp::Ordering::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { //if expr println!("{}", $x); }; } macro_rules! vp { // vector print separate with space ($x:expr) => { println!( "{}", $x.iter() .map(|x| x.to_string()) .collect::>() .join(" ") ); }; } macro_rules! d { ($x:expr) => { eprintln!("{:?}", $x); }; } macro_rules! yn { ($val:expr) => { if $val { println!("Yes"); } else { println!("No"); } }; } macro_rules! map{ // declear btreemap ($($key:expr => $val:expr),*) => { { let mut map = ::std::collections::BTreeMap::new(); $( map.insert($key, $val); )* map } }; } macro_rules! set{ // declear btreemap ($($key:expr),*) => { { let mut set = ::std::collections::BTreeSet::new(); $( set.insert($key); )* set } }; } fn main() { solve(); } // use str::Chars; #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat(n: u32) -> Vec> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readff() -> (f64, f64) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } fn readcc() -> (char, char) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } fn readuuu() -> (usize, usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readiiii() -> (i64, i64, i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } fn read_imat(h: usize) -> Vec> { (0..h).map(|_| read_vec()).collect() } fn read_cmat(h: usize) -> Vec> { (0..h).map(|_| read::().chars().collect()).collect() } pub struct Dsu { n: usize, // root node: -1 * component size // otherwise: parent parent_or_size: Vec, } impl Dsu { // 0 <= size <= 10^8 is constrained. pub fn new(size: usize) -> Self { Self { n: size, parent_or_size: vec![-1; size], } } pub fn merge(&mut self, a: usize, b: usize) -> usize { assert!(a < self.n); assert!(b < self.n); let (mut x, mut y) = (self.leader(a), self.leader(b)); if x == y { return x; } if -self.parent_or_size[x] < -self.parent_or_size[y] { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] += self.parent_or_size[y]; self.parent_or_size[y] = x as i32; x } pub fn same(&mut self, a: usize, b: usize) -> bool { assert!(a < self.n); assert!(b < self.n); self.leader(a) == self.leader(b) } pub fn leader(&mut self, a: usize) -> usize { assert!(a < self.n); if self.parent_or_size[a] < 0 { return a; } self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32; self.parent_or_size[a] as usize } pub fn size(&mut self, a: usize) -> usize { assert!(a < self.n); let x = self.leader(a); -self.parent_or_size[x] as usize } pub fn groups(&mut self) -> Vec> { let mut leader_buf = vec![0; self.n]; let mut group_size = vec![0; self.n]; for i in 0..self.n { leader_buf[i] = self.leader(i); group_size[leader_buf[i]] += 1; } let mut result = vec![Vec::new(); self.n]; for i in 0..self.n { result[i].reserve(group_size[i]); } for i in 0..self.n { result[leader_buf[i]].push(i); } result .into_iter() .filter(|x| !x.is_empty()) .collect::>>() } } fn solve() { let (h, w, n, d) = readuuuu(); let mut dsu = Dsu::new(n); let d = d as i64; let mut points = vec![]; let mut point_to_idx = map![]; let mut idx_to_point = map![]; let mut vec_point_to_idx = vec![vec![INF as usize; (w) as usize]; (h) as usize]; for i in 0..n { let (a, b) = readii(); points.push((a - 1, b - 1, i)); point_to_idx.insert((a - 1, b - 1), i); idx_to_point.insert(i, (a - 1, b - 1)); vec_point_to_idx[a as usize - 1][b as usize - 1] = i; } let mut sign = set![]; for i in 0..n { let (x, y, idx) = points[i]; for dx in -d..=d { for dy in -d..=d { if dx.abs() + dy.abs() > d { continue; } let nx = x as i64 + dx; let ny = y as i64 + dy; if nx < 0 || ny < 0 || nx >= h as i64 || ny >= w as i64 { continue; } if vec_point_to_idx[nx as usize][ny as usize] != INF as usize { let idx2 = vec_point_to_idx[nx as usize][ny as usize]; if dsu.same(idx, idx2) { continue; } if idx == idx2 { continue; } // d!((idx, idx2, x, y, nx, ny, dx, dy)); dsu.merge(idx, idx2); sign.insert(idx); sign.insert(idx2); } } } } let mut star = set![]; // d!((sign.clone())); for i in 0..n { if !sign.contains(&i) { star.insert(i); } } let mut sign_set = set! {}; for &idx in &sign { let leader = dsu.leader(idx); sign_set.insert(leader); } let sign_num = sign_set.len(); let mut max_sign_num = 0; let mut min_sign_num = INF; let mut is_sign = vec![vec![0 as usize; (w) as usize]; (h) as usize]; let mut is_star = vec![vec![0 as usize; (w) as usize]; (h) as usize]; let mut group = vec![vec![0 as usize; (w) as usize]; (h) as usize]; for i in 0..n { let (x, y, idx) = points[i]; let leader = dsu.leader(idx); if sign.contains(&idx) { is_sign[x as usize][y as usize] = 1; group[x as usize][y as usize] = leader; } else { is_star[x as usize][y as usize] = 1; } } // d!((sign)) for i in 0..h as i64 { for j in 0..w as i64 { let mut local_sign_set = set! {}; let mut nsign = 0; let mut nstar = 0; if point_to_idx.contains_key(&(i, j)) { continue; } for di in -d..=d { for dj in -d..=d { if di.abs() + dj.abs() > d { continue; } let ni = i + di; let nj = j + dj; if ni < 0 || nj < 0 || ni >= h as i64 || nj >= w as i64 { continue; } // if point_to_idx.contains_key(&(ni, nj)) { // let idx = point_to_idx[&(ni, nj)]; // let leader = dsu.leader(idx); // if sign.contains(&idx) { // local_sign_set.insert(leader); // } else { // nstar += 1; // } // } if is_sign[ni as usize][nj as usize] == 1 { let leader = group[ni as usize][nj as usize]; local_sign_set.insert(leader); } else if is_star[ni as usize][nj as usize] == 1 { nstar += 1; } } } nsign = local_sign_set.len(); let mut num = 0; if nsign == 0 { if nstar == 0 { num = sign_num; } else { num = sign_num + 1; } } else { num = sign_num - nsign + 1; } // d!((i, j, num, sign_num, nsign, nstar)); max_sign_num = max(max_sign_num, num as i64); min_sign_num = min(min_sign_num, num as i64); } } // d!(sign_num); println!("{} {}", min_sign_num, max_sign_num); }