https://atcoder.jp/contests/abc157/tasks/abc157_f
前提知識
解説
https://atcoder.jp/contests/abc157/submissions/10473747
まず、答えである最小時間であるが、最小時間を境にしてokとngが分かれているので、
答えとなる必要な最小時間で二分探索をしよう。
時間が固定になると嬉しいことがある。
ci * (ある点と熱源との距離) = 時間
となっているが、これが、
(ある点と熱源との距離) = 時間 / ci
のように変形でき、ある点に対して熱源を置ける場所が円の中に限定される。
よって、あとは、そうして作ったすべての円に対して、共通領域を求め、その面積が0より大きければ、
その最小時間で熱源を配置できるということになる。
…が、円の合成はあきらかに難しそう。
ICPCなどで幾何問題に慣れている人はここから発想の飛躍ができる。
熱源は極端なところに置いておけばいいのではないか?
具体的には円と円の交点に置けばよいのではないか?
幾何問題全般で言える話であるが、実数で座標を扱う場合は、候補が極端に多くなる。
なので、一定の仮定を置かないと解けない場合がほとんど。
その時に使う仮定が、大体交点とか接点とかである。
理屈としては、うまいこと移動させたり、境界ギリギリを狙うと、接点になるとか、そういう理屈。
なので、熱源として以下の候補をチェックして、その熱源を使って焼ける肉がK枚以上あれば、その時間はtrue。
- 肉の座標
- ある2つの肉の円が作る交点
EPSを使わないと誤差で死ぬ。
具体的には、A≦Bと書きたいときは、A≦B+EPSとしてやらないと死ぬ。
自分はEPS=1-8でやってる。
int N, K, X[60], Y[60], C[60]; P points[60]; //--------------------------------------------------------------------------------------------------- bool check(double time) { vector<P> cand; rep(i, 0, N) cand.push_back(points[i]); rep(a, 0, N) rep(b, a + 1, N) { auto vp = circle_circle_intersect(points[a], time / C[a], points[b], time / C[b]); cand.push_back(vp.first); cand.push_back(vp.second); } fore(c, cand) { int cnt = 0; rep(i, 0, N) { double req = abs(c - points[i]) * C[i]; if (req <= time + EPS) cnt++; } if (K <= cnt) return true; } return false; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; rep(i, 0, N) cin >> X[i] >> Y[i] >> C[i]; rep(i, 0, N) points[i] = P(X[i], Y[i]); double ng = 0, ok = infl; rep(_, 0, 101) { double md = (ng + ok) / 2; if (check(md)) ok = md; else ng = md; } printf("%.10f\n", ok); }