AtCoder Regular Contest 049 B - 高橋ノルム君
解法
二分探索します。
「時間 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; }