Prob G
#include <bits/stdc++.h> | |
using namespace std; | |
#define rep(i,n) for (int i = 0; i < (int)(n); i++) | |
typedef long long ll; | |
typedef pair <int, int> PII; | |
const int N = 1005; | |
const double eps = 1e-9; | |
double dis(double x, double y) { | |
return sqrt(x * x + y * y); | |
} | |
int main() { | |
int Tc, n, h, w; | |
int d[N], v[N]; | |
ll a[N]; | |
scanf("%d", &Tc); | |
rep (ri, Tc) { | |
scanf("%d%d%d", &n, &h, &w); | |
rep (i, n) scanf("%d", &d[i]); | |
rep (i, n) scanf("%d", &v[i]); | |
double l = 0, r = 1.0 / (max(w, *max_element(v, v + n))); | |
rep (o, 100) { | |
double mid = (l + r) / 2; | |
double sum = 0; | |
rep (i, n) { | |
double tmp = mid * v[i]; | |
tmp *= tmp; | |
assert(1 - tmp > 0); | |
double res = sqrt((tmp * d[i] * d[i]) / (1 - tmp)); | |
sum += res; | |
if (sum > h) break; | |
} | |
if (sum > h) { | |
r = mid; | |
} else { | |
l = mid; | |
} | |
} | |
set < pair <double, int> > ms; | |
ll sum = 0; | |
rep (i, n) { | |
double tmp = l * v[i]; | |
tmp *= tmp; | |
assert(1 - tmp > 0); | |
ll res = max(0.0, sqrt((tmp * d[i] * d[i]) / (1 - tmp)) - 5); | |
a[i] = res; | |
sum += res; | |
ms.insert(make_pair((dis(d[i], res + 1) - dis(d[i], res)) / v[i], i)); | |
} | |
while (sum < h && ms.begin()->first < (1.0 / w)) { | |
pair <double, int> e = *ms.begin(); | |
ms.erase(ms.begin()); | |
int i = e.second; | |
a[i]++; | |
ms.insert(make_pair((dis(d[i], a[i] + 1) - dis(d[i], a[i])) / v[i], i)); | |
sum++; | |
} | |
double ans = (h - sum) / (double)w; | |
rep (i, n) { | |
ans += dis(a[i], d[i]) / v[i]; | |
} | |
printf("Case #%d: %.12f\n", ri + 1, ans); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment