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