fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define X first
  4. #define Y second
  5. #define eb push_back
  6. #define siz(a) int(a.size())
  7. #define endl "\n"
  8.  
  9. #define trace2(x, y)             cerr <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
  10. #define trace3(x, y, z)          cerr <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
  11. #define trace4(a, b, c, d)       cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
  12. #define trace5(a, b, c, d, e)    cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
  13.  
  14. using namespace std;
  15.  
  16. typedef long long int ll;
  17. typedef vector < int > vi;
  18. typedef vector < ll > vll;
  19.  
  20. const int mod=1e9+7;
  21. const int maxn=1e6+5;
  22.  
  23. /*	finding inverse upto n
  24.  * for i in xrange(2, N):
  25.     ifc[i] = -(mod / i) * ifc[mod % i] % mod
  26.  * 
  27. */
  28. ll power(ll base, ll exp, ll mod){ll res = 1; while(exp){if(exp%2)res*=base;base*=base;res%=mod;base%=mod;exp/=2;}return res;}
  29.  
  30. ll t, n, v[maxn], x[maxn];
  31. double dp[2][55];
  32.  
  33. vector<pair<ll, ll> > vv;
  34.  
  35. double go(int idx, bool dir){
  36. 	if(idx == n+1)
  37. 		return (double)1e18;
  38.  
  39. 	double &ret = dp[dir][idx];
  40.  
  41. 	if(ret != -1)
  42. 		return ret;
  43.  
  44. 	for(int i = 0; i<2; i++){
  45. 		if(idx == 1){
  46. 			ret = max(ret, go(idx+1, i));
  47. 		}
  48. 	}	
  49. 		//left
  50. 		if(dir){
  51.  
  52. 			double ans = 1e18;
  53.  
  54. 			if(v[idx] > v[idx-1]){
  55. 				ans = 1.0*(x[idx] - x[idx-1])/(v[idx] - v[idx-1]);
  56. 			} else if(v[idx] == v[idx-1]){
  57. 				if(x[idx] == x[idx-1])
  58. 					ans = 0;
  59. 			}
  60. 			ret = max(ret, min(go(idx+1, dir), ans));
  61.  
  62. 			ret = max(ret, go(idx+1, !dir));
  63. 		} else{
  64. 			double ans = 1e18;
  65.  
  66. 			if(v[idx] < v[idx-1]){
  67. 				ans = -1.0*(x[idx] - x[idx-1])/(v[idx] - v[idx-1]);
  68. 			} else if(v[idx] == v[idx-1]){
  69. 				if(x[idx] == x[idx-1])
  70. 					ans = 0;
  71. 			}
  72.  
  73. 			ret = max(ret, min(go(idx+1, dir), ans));
  74.  
  75. 			ans = 1.0*(x[idx] - x[idx-1])/(v[idx] + v[idx-1]);
  76.  
  77. 			ret = max(ret , min(go(idx+1, !dir), ans));
  78. 		}
  79.  
  80. 	return ret;
  81. }
  82.  
  83. int main(){
  84. 	ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
  85. 	//freopen("input.in", "r", stdin);freopen("output.out", "w", stdout);	
  86. 	cin >> t;
  87.  
  88. 	while(t--){
  89. 		cin >> n;
  90. 		vv.clear();
  91. 		for(int i=1; i<=n; i++){
  92. 			cin >> x[i] >> v[i];
  93. 			dp[0][i] = -1;
  94. 			dp[1][i] = -1;
  95. 			vv.eb({x[i], v[i]});
  96. 		}
  97.  
  98. 		sort(vv.begin(), vv.end());
  99.  
  100. 		for(int i=1; i<=n; i++){
  101. 			x[i] = vv[i-1].X;
  102. 			v[i] = vv[i-1].Y;
  103. 		}
  104.  
  105. 		double ans = go(1, 0);
  106.  
  107. 		if(ans >= 1e17)
  108. 			cout << -1 << endl;
  109. 		else
  110. 			cout << fixed << setprecision(10) <<  ans << endl;
  111. 	}
  112.  
  113. 	return 0;
  114. }
  115.  
Success #stdin #stdout 0s 4248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uA2Oim
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!