Advertisement
Guest User

time_search

a guest
Mar 23rd, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. vector<int>left_end;
  5. vector<int>right_end;
  6. int x, y;
  7. int n, c;
  8. bool res;
  9. vector<int>coord;
  10. vector<int>speed;
  11. bool cross_search(long double t)
  12. {
  13. for (int i = 0; i < n; i++)
  14. {
  15. x = coord[i] - speed[i] * t;
  16. left_end.push_back(x);
  17. y = coord[i] + speed[i] * t;
  18. right_end.push_back(y);
  19. }
  20. int maxi = left_end[0];
  21. int mini = right_end[0];
  22. for (int i = 1; i < n; i++)
  23. {
  24. if (left_end[i] > maxi)
  25. maxi = left_end[i];
  26. }
  27. for (int i = 1; i < n; i++)
  28. {
  29. if (right_end[i] < mini)
  30. mini = right_end[i];
  31. }
  32. if (maxi <= mini)
  33. return true;
  34. else
  35. return false;
  36. }
  37. int main()
  38. {
  39.  
  40. cin >> n;
  41. coord.resize(n);
  42. speed.resize(n);
  43. left_end.resize(n);
  44. right_end.resize(n);
  45. for (int i = 0; i < n; i++)
  46. {
  47. cin >> c;
  48. coord.push_back(c);
  49. }
  50. for (int i = 0; i < n; i++)
  51. {
  52. cin >> c;
  53. speed.push_back(c);
  54. }
  55. double l, r, m;
  56. l = 0;
  57. r = 1000000000;
  58. while ((l - r - 1) > 0,0000001)
  59. {
  60. m = (l + r) / 2;
  61. res = cross_search(m);
  62. if (res)
  63. r = m;
  64. else
  65. l = m;
  66. }
  67. cout << r;
  68. return(0);
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement