Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <iomanip>
- using Matrix = std::vector<std::vector<int>>;
- double result(double time, int quantityOfSegments, Matrix& arrayOfTimesAndSpeeds) {
- double answer{}, now{};
- for (int i{}; i < quantityOfSegments; ++i) {
- if (now + arrayOfTimesAndSpeeds[0][i] < time) {
- now += arrayOfTimesAndSpeeds[0][i];
- answer += arrayOfTimesAndSpeeds[1][i] * arrayOfTimesAndSpeeds[0][i];
- } else {
- answer += (time - now) * arrayOfTimesAndSpeeds[1][i];
- break;
- }
- }
- return answer;
- }
- bool isMiddleCorrect(double middle, int quantityOfSegments, Matrix& arrayOfTimesAndSpeeds, int length) {
- double temporaryTime{}, times{};
- for (int i{}; i < quantityOfSegments; ++i) {
- times += arrayOfTimesAndSpeeds[0][i];
- }
- for (int i{}; i < quantityOfSegments; ++i) {
- temporaryTime += arrayOfTimesAndSpeeds[0][i];
- if (temporaryTime >= middle) {
- double lengthFirst{ result(temporaryTime, quantityOfSegments, arrayOfTimesAndSpeeds) -
- result(temporaryTime - middle, quantityOfSegments, arrayOfTimesAndSpeeds) };
- double lengthSecond{ result(temporaryTime + middle, quantityOfSegments, arrayOfTimesAndSpeeds) -
- result(temporaryTime, quantityOfSegments, arrayOfTimesAndSpeeds) };
- if (temporaryTime + middle > times) {
- lengthSecond = length;
- }
- if (lengthFirst < length || lengthSecond < length) {
- return false;
- }
- }
- }
- double possibleLength = result(middle, quantityOfSegments, arrayOfTimesAndSpeeds);
- if (possibleLength < length) {
- return false;
- }
- return true;
- }
- double search(int quantityOfSegments, Matrix& arrayOfTimesAndSpeeds, int length) {
- double right{}, left{};
- for (int i{}; i < quantityOfSegments; ++i) {
- right += arrayOfTimesAndSpeeds[0][i];
- }
- while (right - left > 0.0001) {
- double middle{ left + (right - left) / 2 };
- (isMiddleCorrect(middle, quantityOfSegments, arrayOfTimesAndSpeeds, length)) ? right = middle : left = middle;
- }
- return right;
- }
- int main() {
- int distance, quantityOfSegments, time, speed;
- std::cin >> distance >> quantityOfSegments;
- Matrix arrayOfTimesAndSpeeds(2);
- for (int i{}; i < 2; ++i) {
- arrayOfTimesAndSpeeds[i] = std::vector<int>(quantityOfSegments);
- }
- for (int i{}; i < quantityOfSegments; ++i) {
- std::cin >> time >> speed;
- arrayOfTimesAndSpeeds[0][i] = time;
- arrayOfTimesAndSpeeds[1][i] = speed;
- }
- std::cout << std::fixed << std::setprecision(3) << search(quantityOfSegments, arrayOfTimesAndSpeeds, distance);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement