アルゴリズムと数学 070

https://atcoder.jp/contests/math-and-algorithm/tasks/abc075_d

ナイーブな実装でも余裕で間に合っていますが、次のようにすると速いです。
xでソートしてxの範囲を固定します。その範囲の中のyを取り出します。その中のK個を取り出すためにスライドして、yの範囲が最小なものを得ます。

// Axis-Parallel Rectangle
#![allow(non_snake_case)]

use std::collections::BTreeSet;


//////////////////// 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()
}


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

type Point = (i64, i64);

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

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

fn calc_min_height(tree: &BTreeSet<i64>, K: usize) -> i64 {
    let ys: Vec<i64> = tree.iter().map(|&y| y).collect();
    let L = ys.len();
    (0..L-K+1).map(|j| ys[j+K-1] - ys[j]).min().unwrap()
}

fn f(K: usize, mut points: Vec<Point>) -> i64 {
    let N = points.len();
    points.sort();
    let mut min_area = 4 * 10i64.pow(18);
    for i1 in 0..N {
        let mut ys: BTreeSet<i64> = BTreeSet::new();
        for i2 in i1..N {
            ys.insert(points[i2].1);
            if i2 - i1 + 1 < K {
                continue
            }
            let W = points[i2].0 - points[i1].0;
            let area = W * calc_min_height(&ys, K);
            if area < min_area {
                min_area = area
            }
        }
    }
    min_area
}

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