Advertisement
Guest User

Untitled

a guest
Oct 18th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <iomanip>
  7. #include <numeric>
  8. #include <cmath>
  9.  
  10. using namespace std;
  11.  
  12. bool checkTiming(double timing, double maxTiming, vector<int> timings,
  13.         vector<int> speeds, int l) {
  14.     double train1 = 0.0;
  15.     double train2 = 0.0;
  16.     double time1 = 0.0;
  17.     double time2 = 0.0;
  18.     int train1Step = 0;
  19.     double firstTiming = timing;
  20.     while (firstTiming > 0) {
  21.         firstTiming -= (double) timings[train1Step];
  22.         train1Step++;
  23.     }
  24.     firstTiming += (double) timings[--train1Step];
  25.     for (int i = 0; i < train1Step; i++) {
  26.         train1 += (double) timings[i] * (double) speeds[i];
  27.         time1 += (double) timings[i];
  28.     }
  29.     train1 += (double) firstTiming * (double) speeds[train1Step];
  30.     int i = 0;
  31.     int it1 = i + train1Step;
  32.     int it2 = i;
  33.     time1 += firstTiming;
  34.     double currentTime1 = firstTiming;
  35.     double currentTime2 = 0.0;
  36.     if (train1 - train2 < (double) l) {
  37.         return false;
  38.     }
  39.     while (time1 < maxTiming) {
  40.         double extraTime1 = (double) timings[it1] - currentTime1;
  41.         train1 += extraTime1 * (double) speeds[it1++];
  42.         time1 += extraTime1;
  43.         while (extraTime1 > 0) {
  44.             if ((double) timings[it2] - currentTime2 < extraTime1) {
  45.                 time2 += (double) timings[it2] - currentTime2;
  46.                 train2 += ((double) timings[it2] - currentTime2)
  47.                         * (double) speeds[it2];
  48.                 extraTime1 -= (double) timings[it2] - currentTime2;
  49.                 currentTime2 = 0.0;
  50.                 it2++;
  51.             } else {
  52.                 time2 += extraTime1;
  53.                 currentTime2 += extraTime1;
  54.                 train2 += extraTime1 * (double) speeds[it2];
  55.                 extraTime1 = 0.0;
  56.             }
  57.         }
  58.         if (train1 - train2 < (double) l)
  59.             return false;
  60.         currentTime1 = 0.0;
  61.         //cout << time1 << " " << time2 << " " << train1 << " " << train2 << endl;
  62.     }
  63.     return true;
  64. }
  65.  
  66. double binsearch(double& left, double& right, vector<int> timings,
  67.         double maxTiming, vector<int> speeds, int l) {
  68.     double c = right;
  69.     while (right - left > 0.001) {
  70.         double mid = (right + left) / 2;
  71.         //cout << mid << endl;
  72.         bool v = checkTiming(mid, maxTiming, timings, speeds, l);
  73.         if (v) {
  74.             if (mid < c)
  75.                 c = mid;
  76.             right = mid;
  77.         } else {
  78.             left = mid;
  79.         }
  80.     }
  81.     return (right + left) / 2;
  82. }
  83. int main() {
  84.     ifstream reader("trains.in");
  85.     ofstream writer("trains.out");
  86.     int l, n;
  87.     reader >> l >> n;
  88.     vector<int> timings;
  89.     vector<int> speeds;
  90.     for (int i = 0; i != n; i++) {
  91.         int timing;
  92.         int speed;
  93.         reader >> timing;
  94.         reader >> speed;
  95.         timings.push_back(timing);
  96.         speeds.push_back(speed);
  97.     }
  98.     double time = (double) accumulate(timings.begin(), timings.end(), 0.0);
  99.     double left = 0.0;
  100.     double value;
  101.     value = binsearch(left, time, timings, time, speeds, l);
  102.     writer << fixed << setprecision(3) << value;
  103.     //cout<<endl;
  104.     //cout << checkTiming (27.5, time, timings, speeds, l);
  105.     writer.close();
  106.     return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement