https://atcoder.jp/contests/abc157/tasks/abc157_f
二次元空間上に$N$枚の肉があり、それぞれの肉は火の通りにくさ$c$というパラメータを持っている。ここで、好きな場所に熱源を置くことを考える。点($X, Y$)に熱源があるとき、点($x, y$)にある肉を焼くためには $$c\sqrt{ (X-x)^2 + (Y-y)^2 }$$ の時間がかかる。$K$枚以上の肉を焼くためにかかる時間の最小値を求めよ。
肉が($x, y$)にあるとき、時間T以内に肉が焼けるためには熱源が肉の位置を中心とした半径$T/c$の円の中になくてはならない。ここで、$K$枚以上の肉を焼くことができる最小の時間$T$を二分探索することを考える。
時間T以内に$K$枚の肉を焼くことが可能であるためには、各肉に対して半径$T/c$の円を描いたときに、$K$個以上の円が重なる座標があればよい。そのような点があるかどうかを判定するためには、円どうしのすべての交点とすべての円の中心を調べればよい(参考:kyopro_friends氏のツイート)。
2円の交点はO($N^2$)で列挙できるから、O($N^3$)でこの問題が解けた(参考:円と円の交点を求める)。
幾何は難しい……。