AtCoder Beginner Contest 330 F

https://atcoder.jp/contests/abc330/tasks/abc330_f

辺の間隔（＝長さ）を一定とすると、辺をずらすとどこかで移動量の最小値がありますが、片方の辺を端からずらしていくと移動量が下に凸になるので、両方の辺を合わせても下に凸になります。なので、領域を3分割して再帰的に最小値を求めていきます。

// Minimize Bounding Square
#![allow(non_snake_case)]

use std::cmp::{min, max};
use std::collections::BTreeMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Motion ////////////////////

struct Motion {
    acc: Vec<(i64, i64, i64)>,
    max_x: i64
}

impl Motion {
    fn new(freq: &Vec<(i64, i64)>) -> Motion {
        let mut acc: Vec<(i64, i64, i64)> = vec![];
        let mut prev_x: i64 = 0;
        let mut s: i64 = 0;
        let mut n: i64 = 0;
        for &(x, f) in freq.iter() {
            s += n * (x - prev_x);
            n += f;
            prev_x = x;
            acc.push((x, s, n))
        }
        Motion { acc, max_x: prev_x }
    }
    
    fn bin_search(&self, first: usize, last: usize, x: i64) -> i64 {
        if last - first == 1 {
            let (x1, s, n) = self.acc[first];
            s + (x - x1) * n
        }
        else {
            let mid = (first + last) / 2;
            let x1 = self.acc[mid].0;
            if x < x1 {
                self.bin_search(first, mid, x)
            }
            else {
                self.bin_search(mid, last, x)
            }
        }
    }
    
    fn value(&self, x: i64) -> i64 {
        if x <= 0 {
            0
        }
        else if x >= self.max_x {
            let (_, s, n) = self.acc.last().unwrap();
            s + n * (x - self.max_x)
        }
        else {
            self.bin_search(0, self.acc.len(), x)
        }
    }
}

//////////////////// WallPair ////////////////////

struct WallPair {
    min_x: i64,
    max_x: i64,
    motion1: Motion,
    motion2: Motion,
}

impl WallPair {
    fn new(xs: Vec<i64>) -> WallPair {
        let min_x = xs.iter().map(|&x| x).min().unwrap();
        let max_x = xs.iter().map(|&x| x).max().unwrap();
        let freq = Self::frequency(&xs);
        let freq1 = freq.iter().
                    map(|&(x, f)| (x-min_x, f)).collect::<Vec<_>>();
        let freq2 = freq.iter().rev().
                    map(|&(x, f)| (max_x-x, f)).collect::<Vec<_>>();
        let motion1 = Motion::new(&freq1);
        let motion2 = Motion::new(&freq2);
        WallPair { min_x, max_x, motion1, motion2 }
    }
    
    fn frequency(xs: &Vec<i64>) -> Vec<(i64, i64)> {
        let mut freq: BTreeMap<i64, i64> = BTreeMap::new();
        for &x in xs.iter() {
            let e = freq.entry(x).or_insert(0);
            *e += 1
        }
        freq.into_iter().collect::<Vec<_>>()
    }
    
    fn value(&self, x: i64, L: i64) -> i64 {
        self.motion1.value(x - self.min_x) +
        self.motion2.value(self.max_x - x - L)
    }
    
    fn size(&self) -> i64 {
        self.max_x - self.min_x
    }
    
    fn bin_search(&self, first: i64, last: i64, L: i64) -> i64 {
        if last - first == 1 {
            self.value(first, L)
        }
        else if last - first == 2 {
            let m1 = self.value(first, L);
            let m2 = self.value(first + 1, L);
            min(m1, m2)
        }
        else {
            let mid1 = (first*2 + last) / 3;
            let mid2 = (first + last*2) / 3;
            let m1 = self.value(mid1, L);
            let m2 = self.value(mid2, L);
            if m1 < m2 {
                self.bin_search(first, mid2, L)
            }
            else {
                self.bin_search(mid1, last, L)
            }
        }
    }
    
    // 辺の長さがLのときの移動量の最小値
    fn min_motion(&self, L: i64) -> i64 {
        if L >= self.max_x - self.min_x {
            0
        }
        else {
            self.bin_search(self.min_x, self.max_x - L + 1, L)
        }
    }
}


//////////////////// process ////////////////////

type Point = (i64, i64);

fn read_point() -> Point {
    let v = read_vec();
    (v[0], v[1])
}

fn read_input() -> (i64, Vec<Point>) {
    let v = read_vec();
    let (N, K) = (v[0], v[1]);
    let points: Vec<Point> = (0..N).map(|_| read_point()).collect();
    (K, points)
}

fn F(K: i64, points: Vec<Point>) -> i64 {
    let xs: Vec<i64> = points.iter().map(|&(x, _)| x).collect();
    let ys: Vec<i64> = points.iter().map(|&(_, y)| y).collect();
    let wall_x = WallPair::new(xs);
    let wall_y = WallPair::new(ys);
    
    // (first, mid]
    let mut first: i64 = -1;
    let mut last: i64 = max(wall_x.size(), wall_y.size());
    while last - first > 1 {
        let mid = (first + last) / 2;
        if wall_x.min_motion(mid) + wall_y.min_motion(mid) <= K {
            last = mid
        }
        else {
            first = mid
        }
    }
    last
}

fn main() {
    let (K, points) = read_input();
    println!("{}", F(K, points))
}