📌

B - Emblem

2023/11/03に公開

この問題はユークリッド距離を使用することで解くことができる

ユークリッド距離

2 点間の直接距離を計算するのに使用される

2 つの点が(x1, y1), (x2, y2)の場合、その距離は

\sqrt{(x2 - x1)^2 + (y2 - y1)^2}

で求められる

最も小さい円の半径の最大化を求めるため、

両方とも半径が決まっている場合

半径が最も小さい円の半径

片方だけ半径が決まっている場合

2 点間の距離をユークリッド距離を使用して求め、半径を引いたもの

両方決まっていない場合

2 点間の距離をユークリッド距離を使用して求め、2 で割ったもの

2 で割る理由は最小の円を最大化するため

ここで決まった最も小さい値が答えとなる

解答

use proconio::input;

#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize,
        M: usize,
        xyr: [(f64, f64, f64); N],
        xy: [(f64, f64); M],
    };
    let max = f64::MAX;
    let mut ans = max;
    for i in 0..M {
        for j in 0..N {
            let (x, y) = xy[i];
            let (x2, y2, r) = xyr[j];
            let tmp = ((x2 - x).abs().powi(2) + (y2 - y).abs().powi(2)).sqrt() - r;
            ans = ans.min(tmp);
        }
        for j in i + 1..M {
            let (x, y) = xy[i];
            let (x2, y2) = xy[j];
            let tmp = ((x2 - x).abs().powi(2) + (y2 - y).abs().powi(2)).sqrt() / 2.0;
            ans = ans.min(tmp);
        }
    }
    for i in 0..N {
        ans = ans.min(xyr[i].2);
    }
    println!("{}", ans);
}
GitHubで編集を提案

Discussion