Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <sstream>
- #include <vector>
- #include <algorithm>
- #include <iomanip>
- #include <numeric>
- #include <cmath>
- using namespace std;
- bool checkTiming(double timing, double maxTiming, vector<int> timings,
- vector<int> speeds, int l) {
- double train1 = 0.0;
- double train2 = 0.0;
- double time1 = 0.0;
- double time2 = 0.0;
- int train1Step = 0;
- double firstTiming = timing;
- while (firstTiming > 0) {
- firstTiming -= (double) timings[train1Step];
- train1Step++;
- }
- firstTiming += (double) timings[--train1Step];
- for (int i = 0; i < train1Step; i++) {
- train1 += (double) timings[i] * (double) speeds[i];
- time1 += (double) timings[i];
- }
- train1 += (double) firstTiming * (double) speeds[train1Step];
- int i = 0;
- int it1 = i + train1Step;
- int it2 = i;
- time1 += firstTiming;
- double currentTime1 = firstTiming;
- double currentTime2 = 0.0;
- if (train1 - train2 < (double) l) {
- return false;
- }
- while (time1 < maxTiming) {
- double extraTime1 = (double) timings[it1] - currentTime1;
- train1 += extraTime1 * (double) speeds[it1++];
- time1 += extraTime1;
- while (extraTime1 > 0) {
- if ((double) timings[it2] - currentTime2 < extraTime1) {
- time2 += (double) timings[it2] - currentTime2;
- train2 += ((double) timings[it2] - currentTime2)
- * (double) speeds[it2];
- extraTime1 -= (double) timings[it2] - currentTime2;
- currentTime2 = 0.0;
- it2++;
- } else {
- time2 += extraTime1;
- currentTime2 += extraTime1;
- train2 += extraTime1 * (double) speeds[it2];
- extraTime1 = 0.0;
- }
- }
- if (train1 - train2 < (double) l)
- return false;
- currentTime1 = 0.0;
- //cout << time1 << " " << time2 << " " << train1 << " " << train2 << endl;
- }
- return true;
- }
- double binsearch(double& left, double& right, vector<int> timings,
- double maxTiming, vector<int> speeds, int l) {
- double c = right;
- while (right - left > 0.001) {
- double mid = (right + left) / 2;
- //cout << mid << endl;
- bool v = checkTiming(mid, maxTiming, timings, speeds, l);
- if (v) {
- if (mid < c)
- c = mid;
- right = mid;
- } else {
- left = mid;
- }
- }
- return (right + left) / 2;
- }
- int main() {
- ifstream reader("trains.in");
- ofstream writer("trains.out");
- int l, n;
- reader >> l >> n;
- vector<int> timings;
- vector<int> speeds;
- for (int i = 0; i != n; i++) {
- int timing;
- int speed;
- reader >> timing;
- reader >> speed;
- timings.push_back(timing);
- speeds.push_back(speed);
- }
- double time = (double) accumulate(timings.begin(), timings.end(), 0.0);
- double left = 0.0;
- double value;
- value = binsearch(left, time, timings, time, speeds, l);
- writer << fixed << setprecision(3) << value;
- //cout<<endl;
- //cout << checkTiming (27.5, time, timings, speeds, l);
- writer.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement