AtCoder Regular Contest 049 B - 高橋ノルム君
B - 高橋ノルム君
解法
二分探索。$O(N^2\log N)$。
一点に集まるために必要な最小の時間、を達成するような点は、全ての初期位置から時間$t$以内に到達可能な点である。 逆にそのような最小の時間とは、そのような点が存在するような時間の中で最小のものである。 その点の存在は、任意のふたつの初期位置に関して、それぞれそこから出発して時間$t$以内に集まることができる、で判定できる。
実装
#include <iostream>
#include <vector>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
int n; cin >> n;
vector<ll> x(n), y(n), c(n); repeat (i,n) cin >> x[i] >> y[i] >> c[i];
vector<double> v(n); repeat (i,n) v[i] = 1.0 / c[i];
auto do_intersect = [&](int i, int j, double t) {
return max(abs(x[i] - x[j]), abs(y[i] - y[j])) <= (v[i] + v[j]) * t;
};
double low = 0, high = 1e18;
repeat (iteration,100) {
double mid = (low + high) / 2;
bool p = true;
repeat (i,n) repeat (j,i) {
if (not do_intersect(i, j, mid)) {
p = false;
goto a_break;
}
}
a_break:
(p ? high : low) = mid;
}
printf("%.8lf\n", low);
return 0;
}