Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define FNAME "trains"
- #define _CRT_SECURE_NO_WARNINGS
- #define fi first
- #define se second
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- typedef pair<double, double> pdd;
- const int N = 1e4;
- const double BIN = 1e7 + 7;
- int t[N], v[N];
- vector<pdd> a(N);
- int find_lower(vector<pdd> &a, pair<double, double> val) {
- int l = 0, r = a.size();
- while (r - l > 1) {
- int m = (l + r) / 2;
- a[m].first <= val.first ? l = m : r = m;
- }
- return l;
- }
- int find_upper(vector<pdd> &a, pair<double, double> val) {
- int l = -1, r = a.size() - 1;
- while (r - l > 1) {
- int m = (l + r) / 2;
- a[m].first < val.first ? l = m : r = m;
- }
- return r;
- }
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen(FNAME".in", "r", stdin);
- freopen(FNAME".out", "w", stdout);
- #endif
- ios::sync_with_stdio(false);
- a.clear();
- a.push_back(make_pair(0, 0));
- int l, n;
- cin >> l >> n;
- for (int i = 0; i < n; ++i) {
- cin >> t[i] >> v[i];
- a.push_back(make_pair(a.back().fi + t[i], a.back().se + t[i] * v[i]));
- }
- double bin_l = 0, bin_r = BIN;
- for (int it = 0; it < 1000; ++it) {
- double m = (bin_l + bin_r) / 2;
- bool crushed = false;
- for (int k = 0; k < n; ++k) {
- pdd j = a[k];
- j.fi += m;
- int i = find_lower(a, j);
- if (i == n) {
- break;
- }
- if ((a[i].se + ((j.fi - a[i].fi) * (double)v[i]) - j.se) < (double)l) {
- crushed = true;
- break;
- }
- }
- for (int k = n; k > 0; --k) {
- pdd i = a[k];
- i.fi -= m;
- int j = find_upper(a, i);
- if (j == 0 && i.fi < a[j].fi) {
- break;
- }
- if ((i.se + ((a[j].fi - i.fi) * (double)v[max(0, j - 1)]) - a[j].se) < (double)l) {
- crushed = true;
- break;
- }
- }
- crushed ? bin_l = m : bin_r = m;
- }
- cout << setprecision(3) << fixed << bin_r << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement