Skip to content

Instantly share code, notes, and snippets.

@c650
Created March 2, 2018 21:32
Show Gist options
  • Save c650/b7f4c5ccc446a48fbc181aa387db2c58 to your computer and use it in GitHub Desktop.
Save c650/b7f4c5ccc446a48fbc181aa387db2c58 to your computer and use it in GitHub Desktop.
/*
Problem 6: Drizzle
from the Mercer 2018 Spr Programming contest
Charles Bailey
03 02 2018
*/
#include <bits/stdc++.h>
typedef long long ll;
const double EPI = 1e-6;
struct bg_speed_point {
double point;
bool is_left;
ll id;
bool operator<(const bg_speed_point& o) const {
if (point > o.point)
return true;
if (std::abs(o.point - point) <= EPI) {
if (id != o.id) return !is_left;
return is_left;
}
return false;
}
};
static void one_case(void) {
ll n, x, vmax;
std::scanf("%lld %lld %lld",&n,&x,&vmax);
std::multiset<bg_speed_point> stuff;
double local_max = 0;
for (ll i = 0; i < n; ++i) {
double xi,yi,li,vi;
std::scanf("%lf %lf %lf %lf",&xi,&yi,&li,&vi);
double t1 = yi/vi;
double t2 = (yi + li) / vi;
stuff.insert({xi / t1, true, i});
stuff.insert({xi / t2, false, i});
local_max = std::max(local_max, std::max(xi/t1, xi/t2));
}
double vmaxd = vmax;
stuff.insert({vmaxd, true, n});
stuff.insert({vmaxd, false, n});
double ans = 0;
ll cnt = 0;
if (local_max < vmax)
ans = vmax;
for (auto& e : stuff) {
// std::printf("%s of interval at v = %f (id = %lld)\n", e.is_left ? "OPEN" :"CLOSE", e.point, e.id);
if (cnt == 0 && e.point <= vmaxd) {
ans = std::max(ans,e.point);
}
cnt += e.is_left ? 1 : -1;
if (cnt == 0 && e.point <= vmaxd) {
ans = std::max(ans,e.point);
}
}
// std::printf("----\n");
// std::printf("speed: %f\n", ans);
std::printf("%f\n", x / ans);
}
int main(void) {
ll t;
std::scanf("%lld", &t);
while(t--) one_case();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment