CodeForces - 782B The Meeting Place Cannot Be Changed二分+精度控制

xiaoxiao2021-02-28  147

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double INF = 1e9; const int maxn = 60000 + 10; double n, pos[maxn], v[maxn]; bool check(double t) { double a = pos[0] - v[0] * t, b = pos[0] + v[0] * t; for (int i = 1; i < n; i++) { double x = pos[i] - v[i] * t; double y = pos[i] + v[i] * t; if (x > b || y < a) return false; if (a < x) a = x; if (b > y) b = y; } return true; } int main() { while (scanf("%lf", &n) == 1) { for (int i = 0; i < n; i++) scanf("%lf", &pos[i]); for (int i = 0; i < n; i++) scanf("%lf", &v[i]); double l = 0, r = INF, t, ans = 0; while (r - l > 1e-7) { t = (l + r) / 2.0; if (check(t)) { r = t; ans = t; } else { l = t; } } printf("%lf\n", ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-39891.html

最新回复(0)