Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <stack>
  5. #include <cstring>
  6. #include <map>
  7. #include <string>
  8. #include <cmath>
  9.  
  10. using namespace std;
  11.  
  12. double vremeist(int x1, int x2, int v1, int v2, int dir)
  13. {
  14. if(v1<=v2 && dir==0)
  15. return 1000000006.0;
  16. if(v1>=v2 && dir==1)
  17. return 1000000006.0;
  18.  
  19. return (double)(x1-x2) / (v1-v2);
  20. }
  21. double vremesprotivno(int x1, int x2, int v1, int v2)
  22. {
  23. return (double)(x1-x2) / (v1+v2);
  24. }
  25. int main()
  26. {
  27. int t;
  28. cin>>t;
  29.  
  30. while(t--)
  31. {
  32. cout.precision(6);
  33. int n;
  34. cin>>n;
  35.  
  36. pair<int, int> p[n+6];
  37. for(int i=0; i<n; i++)
  38. {
  39. cin>>p[i].first>>p[i].second;
  40. }
  41. sort(p, p+n);
  42.  
  43. double low = 0.0;
  44. double high = 1000000004.2;
  45. double mid;
  46. bool f;
  47. int dir[n + 2];
  48. double maxi;
  49.  
  50. while(fabs(low-high)>0.000001)
  51. {
  52. mid = (low+high) / 2.0;
  53.  
  54. // cout<<fixed<<low<<"\t"<<mid<<"\t"<<high<<endl;
  55. dir[0] = 0;
  56. f = true;
  57. for(int i=1; i<n; i++)
  58. {
  59. if(dir[i-1]==0)
  60. {
  61. if(vremeist(p[i].first, p[i-1].first, p[i].second, p[i-1].second, 0)>=mid)
  62. dir[i] = 0;
  63. else //if(dir[i-1]==0 && vremesprotivno(p[i].first, p[i-1].first, p[i].second, p[i-1].second)>mid)
  64. dir[i] = 1;
  65. }
  66. else if(dir[i-1] == 1)
  67. {
  68. if(vremesprotivno(p[i].first, p[i-1].first, p[i].second, p[i-1].second)>=mid)
  69. dir[i] = 0;
  70. else if(vremeist(p[i].first, p[i-1].first, p[i].second, p[i-1].second, 1)>=mid)
  71. dir[i] = 1;
  72. else
  73. {
  74. f = false;
  75. break;
  76. }
  77. }
  78. }
  79.  
  80. if(!f)
  81. {
  82. high = mid;
  83. }
  84. else
  85. {
  86. maxi = mid;
  87. low = mid;
  88. }
  89. }
  90.  
  91. if(maxi > 1000000002.0)
  92. cout<<"-1"<<endl;
  93. else
  94. cout<<fixed<<maxi<<endl;
  95. }
  96. return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement