Yakiniku Optimization Problem [AtCoder Beginner Contest 157 F]

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);
}