結果

問題 No.2612 Close the Distance
コンテスト
ユーザー Mitarushi
提出日時 2023-06-16 18:02:59
言語 Rust
(1.83.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,791 bytes
コンパイル時間 20,697 ms
コンパイル使用メモリ 399,848 KB
実行使用メモリ 11,652 KB
最終ジャッジ日時 2024-09-27 19:23:52
合計ジャッジ時間 20,476 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 2 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();

    let n = input.trim().parse::<i64>().unwrap();
    let mut xy = Vec::with_capacity(n as usize);
    for _ in 0..n {
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        let mut input = input.split_whitespace().map(|x| x.parse::<i64>().unwrap());

        let x = input.next().unwrap();
        let y = input.next().unwrap();
        xy.push((x + y, x - y));
    }

    let mut ng = -1;
    let mut ok = 10_000_000_000;

    while ok - ng > 1 {
        let mid = (ok + ng) / 2;
        if is_not_more_than_a(&xy, mid, &vec![], 3) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    println!("{}", ok);
}

fn is_not_more_than_a(xy: &Vec<(i64, i64)>, a: i64, boxes: &Vec<(i64, i64)>, k: i64) -> bool {
    let outer_box = xy.iter().filter(|(x, y)| {
        !boxes
            .iter()
            .any(|(bx, by)| bx <= x && *x <= bx + a && by <= y && *y <= by + a)
    });
    if outer_box.clone().count() <= k as usize {
        return true;
    }
    if k <= 0 {
        return false;
    }

    let x_max = outer_box.clone().map(|(x, _)| x).max().unwrap().clone() - a;
    let x_min = outer_box.clone().map(|(x, _)| x).min().unwrap().clone();
    let y_max = outer_box.clone().map(|(_, y)| y).max().unwrap().clone() - a;
    let y_min = outer_box.clone().map(|(_, y)| y).min().unwrap().clone();

    let next_boxe = vec![
        (x_min, y_min),
        (x_min, y_max),
        (x_max, y_min),
        (x_max, y_max),
    ];

    next_boxe.iter().any(|(x, y)| {
        let mut next_boxes = boxes.clone();
        next_boxes.push((*x, *y));
        is_not_more_than_a(xy, a, &next_boxes, k - 1)
    })
}
0