結果

問題 No.2612 Close the Distance
ユーザー MitarushiMitarushi
提出日時 2023-06-16 18:02:59
言語 Rust
(1.77.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,791 bytes
コンパイル時間 5,738 ms
コンパイル使用メモリ 165,404 KB
実行使用メモリ 11,712 KB
最終ジャッジ日時 2024-01-07 15:36:32
合計ジャッジ時間 10,854 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 5 ms
6,676 KB
testcase_04 AC 4 ms
6,676 KB
testcase_05 AC 4 ms
6,676 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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