Advertisement
Tark_Wight

Untitled

Jun 19th, 2023
36
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.91 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <iomanip>
  4.  
  5.  
  6. using Matrix = std::vector<std::vector<int>>;
  7.  
  8.  
  9. double result(double time, int quantityOfSegments, Matrix& arrayOfTimesAndSpeeds) {
  10. double answer{}, now{};
  11.  
  12. for (int i{}; i < quantityOfSegments; ++i) {
  13. if (now + arrayOfTimesAndSpeeds[0][i] < time) {
  14. now += arrayOfTimesAndSpeeds[0][i];
  15. answer += arrayOfTimesAndSpeeds[1][i] * arrayOfTimesAndSpeeds[0][i];
  16. } else {
  17. answer += (time - now) * arrayOfTimesAndSpeeds[1][i];
  18. break;
  19. }
  20. }
  21. return answer;
  22. }
  23.  
  24.  
  25. bool isMiddleCorrect(double middle, int quantityOfSegments, Matrix& arrayOfTimesAndSpeeds, int length) {
  26. double temporaryTime{}, times{};
  27.  
  28. for (int i{}; i < quantityOfSegments; ++i) {
  29. times += arrayOfTimesAndSpeeds[0][i];
  30. }
  31.  
  32. for (int i{}; i < quantityOfSegments; ++i) {
  33. temporaryTime += arrayOfTimesAndSpeeds[0][i];
  34.  
  35. if (temporaryTime >= middle) {
  36. double lengthFirst{ result(temporaryTime, quantityOfSegments, arrayOfTimesAndSpeeds) -
  37. result(temporaryTime - middle, quantityOfSegments, arrayOfTimesAndSpeeds) };
  38. double lengthSecond{ result(temporaryTime + middle, quantityOfSegments, arrayOfTimesAndSpeeds) -
  39. result(temporaryTime, quantityOfSegments, arrayOfTimesAndSpeeds) };
  40.  
  41. if (temporaryTime + middle > times) {
  42. lengthSecond = length;
  43. }
  44.  
  45. if (lengthFirst < length || lengthSecond < length) {
  46. return false;
  47. }
  48. }
  49. }
  50.  
  51. double possibleLength = result(middle, quantityOfSegments, arrayOfTimesAndSpeeds);
  52.  
  53. if (possibleLength < length) {
  54. return false;
  55. }
  56.  
  57. return true;
  58. }
  59.  
  60.  
  61. double search(int quantityOfSegments, Matrix& arrayOfTimesAndSpeeds, int length) {
  62. double right{}, left{};
  63.  
  64. for (int i{}; i < quantityOfSegments; ++i) {
  65. right += arrayOfTimesAndSpeeds[0][i];
  66. }
  67.  
  68. while (right - left > 0.0001) {
  69. double middle{ left + (right - left) / 2 };
  70. (isMiddleCorrect(middle, quantityOfSegments, arrayOfTimesAndSpeeds, length)) ? right = middle : left = middle;
  71. }
  72.  
  73. return right;
  74. }
  75.  
  76.  
  77. int main() {
  78. int distance, quantityOfSegments, time, speed;
  79. std::cin >> distance >> quantityOfSegments;
  80.  
  81. Matrix arrayOfTimesAndSpeeds(2);
  82.  
  83. for (int i{}; i < 2; ++i) {
  84. arrayOfTimesAndSpeeds[i] = std::vector<int>(quantityOfSegments);
  85. }
  86.  
  87. for (int i{}; i < quantityOfSegments; ++i) {
  88. std::cin >> time >> speed;
  89.  
  90. arrayOfTimesAndSpeeds[0][i] = time;
  91. arrayOfTimesAndSpeeds[1][i] = speed;
  92. }
  93.  
  94.  
  95. std::cout << std::fixed << std::setprecision(3) << search(quantityOfSegments, arrayOfTimesAndSpeeds, distance);
  96.  
  97. return 0;
  98. }
  99.  
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement