Prob G

G.cpp

#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);
    }
}