Created
March 2, 2018 21:32
-
-
Save c650/b7f4c5ccc446a48fbc181aa387db2c58 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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