ABC #157 F
肉 \(i\) が \(T\) 秒以内に焼けるための熱源の位置を考える. これは,
\[c_i \sqrt{(x-x_i)^2 + (y-y_i)^2} \leq T\]なので,
\[(x-x_i)^2 + (y-y_i)^2 \leq \left( \frac{T}{c_i} \right)^2\]となり, 半径 \(T/ci\) の円の内側の部分となる.
\(K\) 枚の肉が \(T\) 秒以内に焼けるということは, \(K\) 枚の肉が焼けるための熱源の位置に共通部分があるということである.
円の共通部分には必ずそのうちの 2 つの円を取り出したときの交点または \(1\) つの円の中心が \(1\) つ以上含まれるので, \(N\) 枚の肉のうち \(2\) つを取り出して交点を求め, その交点および円の中心と他の肉の距離を計算すれば \(K\) 枚焼けるかどうかが分かる. このとき, 他の肉との距離がある数以内かどうかを調べるときにはある数に微小な数を足しておかないと誤差で判定が狂ってしまう.
あとは \(T\) を二分探索で求めればいい.