Skip to content

Instantly share code, notes, and snippets.

@edwardmjm

edwardmjm/G.cpp Secret

Created May 23, 2014 14:28
Show Gist options
  • Save edwardmjm/4a8c8d519b02d6d8a8f1 to your computer and use it in GitHub Desktop.
Save edwardmjm/4a8c8d519b02d6d8a8f1 to your computer and use it in GitHub Desktop.
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