Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.74 KB | None | 0 0
  1. #define FNAME "trains"
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #define fi first
  4. #define se second
  5. #include <iostream>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <iomanip>
  9.  
  10. using namespace std;
  11.  
  12. typedef pair<double, double> pdd;
  13.  
  14. const int N = 1e4;
  15. const double BIN = 1e7 + 7;
  16.  
  17. int t[N], v[N];
  18. vector<pdd> a(N);
  19.  
  20. int find_lower(vector<pdd> &a, pair<double, double> val) {
  21.     int l = 0, r = a.size();
  22.  
  23.     while (r - l > 1) {
  24.         int m = (l + r) / 2;
  25.         a[m].first <= val.first ? l = m : r = m;
  26.     }
  27.  
  28.     return l;
  29. }
  30.  
  31. int find_upper(vector<pdd> &a, pair<double, double> val) {
  32.     int l = -1, r = a.size() - 1;
  33.  
  34.     while (r - l > 1) {
  35.         int m = (l + r) / 2;
  36.         a[m].first < val.first ? l = m : r = m;
  37.     }
  38.  
  39.     return r;
  40. }
  41.  
  42. int main() {
  43. #ifdef _DEBUG
  44.     freopen("input.txt", "r", stdin);
  45.     freopen("output.txt", "w", stdout);
  46. #else
  47.     freopen(FNAME".in", "r", stdin);
  48.     freopen(FNAME".out", "w", stdout);
  49. #endif
  50.     ios::sync_with_stdio(false);
  51.  
  52.     a.clear();
  53.     a.push_back(make_pair(0, 0));
  54.  
  55.     int l, n;
  56.     cin >> l >> n;
  57.     for (int i = 0; i < n; ++i) {
  58.         cin >> t[i] >> v[i];
  59.         a.push_back(make_pair(a.back().fi + t[i], a.back().se + t[i] * v[i]));
  60.     }
  61.  
  62.     double bin_l = 0, bin_r = BIN;
  63.     for (int it = 0; it < 1000; ++it) {
  64.         double m = (bin_l + bin_r) / 2;
  65.  
  66.         bool crushed = false;
  67.         for (int k = 0; k < n; ++k) {
  68.             pdd j = a[k];
  69.             j.fi += m;
  70.  
  71.             int i = find_lower(a, j);
  72.             if (i == n) {
  73.                 break;
  74.             }
  75.             if ((a[i].se + ((j.fi - a[i].fi) * (double)v[i]) - j.se) < (double)l) {
  76.                 crushed = true;
  77.                 break;
  78.             }
  79.         }
  80.         for (int k = n; k > 0; --k) {
  81.             pdd i = a[k];
  82.             i.fi -= m;
  83.  
  84.             int j = find_upper(a, i);
  85.             if (j == 0 && i.fi < a[j].fi) {
  86.                 break;
  87.             }
  88.             if ((i.se + ((a[j].fi - i.fi) * (double)v[max(0, j - 1)]) - a[j].se) < (double)l) {
  89.                 crushed = true;
  90.                 break;
  91.             }
  92.         }
  93.  
  94.         crushed ? bin_l = m : bin_r = m;
  95.     }
  96.  
  97.     cout << setprecision(3) << fixed << bin_r << "\n";
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement