fork(1) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <cmath>
  5. #include <limits>
  6. using namespace std;
  7. vector <int> t, v, x;
  8. int mt = 0, l;
  9.  
  10. double dx(double rt) {
  11. double dx = 0, dt = 0, i = 0;
  12. bool f = true;
  13. while (f) {
  14. if ((i > 0 && dt + t[i] - t[i-1] >= rt) || (dt + t[i] >= rt && !i)){
  15. dx += v[i] * (rt - dt);
  16. f = false;
  17. } else {
  18. dt += (i)?t[i] - t[i-1]:t[0];
  19. dx += x[i++];
  20. }
  21. }
  22. return dx;
  23. }
  24.  
  25. int check(double m) {
  26. double mn = numeric_limits<double>::max();
  27. if (dx(m) < l) return 0;
  28. for (int i = 0; i < t.size(); i++){
  29. if (t[i] >= m){
  30. double s1 = double(x[i] - dx(t[i]-m));
  31. double s2 = (t[i] + m <= mt)?double(dx(t[i]+m) - x[i]):l;
  32. mn = min(mn, min(s1, s2));
  33. }
  34. }
  35. if (mn < l) return false;
  36. else return true;
  37. }
  38.  
  39. double srch(double l, double r) {
  40. while (r - l > 0.00001) {
  41. double mid = 1. * (l + r) / 2;
  42. if (check(mid)) r = mid;
  43. else l = mid;
  44. }
  45. return r;
  46. }
  47.  
  48. int main() {
  49. ifstream cin("trains.in");
  50. ofstream cout("trains.out");
  51. int n, a, b;
  52. double at = 0;
  53. cin >> l >> n;
  54. for (int i = 0; i < n; ++i) {
  55. cin >> a >> b;
  56. t.push_back(a);
  57. v.push_back(b);
  58. x.push_back(t[i] * v[i]);
  59. if (i) {
  60. t[i] += t[i-1];
  61. x[i] += x[i-1];
  62. }
  63. }
  64. mt = t[n-1];
  65. cout << srch(0, double(mt)) << endl;
  66. }
Runtime error #stdin #stdout 0s 3468KB
stdin
1000
4
10 0
30 80
15 0
20 100
stdout
Standard output is empty