AtCoder Regular Contest 049 B - 高橋ノルム君

問題

arc049.contest.atcoder.jp

解法

二分探索します。

「時間 t ですべての頂点が一箇所に集まることが出来るか」というのを判定したいです。

そのために, i 番目の高橋ノルム君がどの範囲を動けるのかをまず調べてみると, これは 「Xi, Yi を中心とする, 一辺の長さが 2*t/C[i] の x 軸, y 軸に平行な正方形」になります。
0, 1, ..., N-1 番目の高橋ノルム君がすべて一箇所に集まるためには, 任意の i, j に対して, 「i が動ける範囲と j が動ける範囲に共通部分がある」ことが必要十分条件です。各 t に対してこれを確かめましょう。

const int MAXN = 1010;
int X[MAXN], Y[MAXN], C[MAXN];
int N;

bool ok(double r) {
    for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) {
        int dy = abs(Y[i]-Y[j]);
        if (dy > r/C[i] + r/C[j]) return false;
        int dx = abs(X[i]-X[j]);
        if (dx > r/C[i] + r/C[j]) return false;
    }
    return true;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i] >> C[i];
    }
    double low = 0, high = 1e9;
    for (int i = 0; i < 50; i++) {
        const double med = (low+high)/2;
        if (ok(med)) high = med;
        else low = med;
    }
    printf("%.10lf\n", high);
    return 0;
}