Advertisement
Guest User

Untitled

a guest
Jul 24th, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.60 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <sstream>
  4. #include <iomanip>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <cctype>
  9. #include <cstring>
  10. #include <vector>
  11. #include <list>
  12. #include <queue>
  13. #include <deque>
  14. #include <stack>
  15. #include <map>
  16. #include <set>
  17. #include <algorithm>
  18. #include <iterator>
  19. #include <bitset>
  20. #include <ctime>
  21. #include<unordered_set>
  22. #include<complex>
  23. using namespace std;
  24.  
  25. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  26. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  27. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  28. #define FILL(a,value) memset(a, value, sizeof(a))
  29.  
  30. #define SZ(a) (int)a.size()
  31. #define ALL(a) a.begin(), a.end()
  32. #define PB push_back
  33. #define MP make_pair
  34.  
  35. typedef long long LL;
  36. typedef unsigned long long ULL;
  37. typedef vector<int> VI;
  38. typedef pair<int, int> PII;
  39.  
  40. const double PI = acos(-1.0);
  41. const int INF = 1000 * 1000 * 1000 + 7;
  42. const LL LINF = INF * (LL)INF;
  43.  
  44. const int MOD = 1000 * 1000 * 1000 + 7;
  45.  
  46. const int MAX = 1000 * 100 + 47;
  47.  
  48. double x[MAX];
  49. double v[MAX];
  50. double t[MAX];
  51. int n;
  52. double s;
  53.  
  54. double getTime(int c)
  55. {
  56. double time1 = LINF;
  57. FOR(i, 0, n)
  58. {
  59. if (t[i] == 1)
  60. {
  61. if (x[i] <= c)
  62. {
  63. double d = (v[i] * c - s * x[i]) / (v[i] - s);
  64. double temp = x[i] / v[i];
  65. if (d > 0)
  66. {
  67. temp = (c - d) / s + d / (s + v[i]);
  68. }
  69.  
  70. time1 = min(time1, temp);
  71. }
  72. else
  73. {
  74. time1 = min(time1, x[i] / v[i]);
  75. }
  76.  
  77. }
  78. }
  79.  
  80. double time2 = LINF;
  81. FOR(i, 0, n)
  82. {
  83. if (t[i] == 2)
  84. {
  85. if (x[i] >= c)
  86. {
  87. double d = (v[i] * c - s * x[i]) / (v[i] - s);
  88. double temp = (1000 * 1000 - x[i]) / v[i];
  89. if (d < 1000 * 1000)
  90. {
  91. temp = (c - d) / s + (1000 * 1000 - d) / (s + v[i]);
  92. }
  93.  
  94. time2 = min(time1, temp);
  95. }
  96. else
  97. {
  98. time2 = min(time2, (1000 * 1000 - x[i]) / v[i]);
  99. }
  100. }
  101. }
  102.  
  103. return max(time1, time2);
  104. }
  105.  
  106. int main()
  107. {
  108. //freopen("in.txt", "r", stdin);
  109. ios::sync_with_stdio(false); cin.tie(0);
  110.  
  111.  
  112. cin >> n >> s;
  113. double minn = INF, maxx = 0;
  114. FOR(i, 0, n)
  115. {
  116. cin >> x[i] >> v[i] >> t[i];
  117. if (t[i] == 1)
  118. {
  119. minn = min(x[i], minn);
  120. }
  121. else
  122. {
  123. maxx = max(maxx, x[i]);
  124. }
  125. }
  126.  
  127. //cout << minn << " " << maxx << endl;
  128. double l = 0, r = 1000 * 1000;
  129. FOR(i, 0, 100)
  130. {
  131. double l1 = l + (r - l) / 3;
  132. double r1 = l + 2 * (r - l) / 3;
  133. if (getTime(l1) > getTime(r1))
  134. {
  135. l = l1;
  136. }
  137. else
  138. {
  139. r = r1;
  140. }
  141. }
  142.  
  143.  
  144. cout << fixed << setprecision(9) << min(getTime(l), getTime(10000000)) << endl;
  145. return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement