📌
B - Emblem
この問題はユークリッド距離を使用することで解くことができる
ユークリッド距離
2 点間の直接距離を計算するのに使用される
2 つの点が(x1, y1), (x2, y2)の場合、その距離は
で求められる
最も小さい円の半径の最大化を求めるため、
両方とも半径が決まっている場合
半径が最も小さい円の半径
片方だけ半径が決まっている場合
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);
}
Discussion