fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool left(vector<int> &x, vector<int> &lft, int pos, int rad){
  6. 	int l = -1, r = pos;
  7. 	while(r - l > 1){
  8. 		int mid = (r + l) / 2;
  9. 		if(x[mid] >= x[pos] - rad)r = mid;
  10. 		else l = mid;
  11. 	}
  12. 	if(r == pos)return false;
  13. 	if(lft[r] > rad - 1)return false;
  14. 	return true;
  15. }
  16.  
  17. bool right(vector<int> &x, vector<int> &rt, int pos, int rad){
  18. 	int l = pos, r = x.size();
  19. 	while(r - l > 1){
  20. 		int mid = (r + l) / 2;
  21. 		if(x[mid] <= x[pos] + rad)l = mid;
  22. 		else r = mid;
  23. 	}
  24. 	if(l == pos)return false;
  25. 	if(rt[l] > rad - 1)return false;
  26. 	return true;
  27. }
  28.  
  29. bool enough(vector<int> &x, vector<int> &lft, vector<int> &rt, double rad){
  30.     int p1 = -1, r = lft.size();
  31.     while(r - p1 > 1){
  32.         int mid = (r + p1) / 2;
  33.         if(lft[mid] <= rad - 1)p1 = mid;
  34.         else r = mid;
  35.     }
  36.     int l = -1, p2 = rt.size();
  37.     while(p2 - l > 1){
  38.         int mid = (p2 + l) / 2;
  39.         if(rt[mid] > rad - 1)l = mid;
  40.         else p2 = mid;
  41.     }
  42.     return x[p2] - x[p1] <= 2 * rad;
  43. }
  44.  
  45. int main() {
  46. 	int n;
  47. 	cin >> n;
  48. 	vector<int> x(n);
  49. 	vector<int> lft(n), rt(n);
  50. 	for(int i = 0; i < n; ++i)cin >> x[i];
  51. 	sort(x.begin(), x.end());
  52. 	for(int i = 1; i < n; ++i){
  53. 		int l = 0, r = 1e10;
  54. 		while(r - l > 1){
  55. 			int mid = (r + l) / 2;
  56. 			if(left(x, lft, i, mid))r = mid;
  57. 			else l = mid;
  58. 		}
  59. 		lft[i] = r;
  60. 	}
  61. 	for(int i = n - 2; i >= 0; --i){
  62. 		int l = 0, r = 1e10;
  63. 		while(r - l > 1){
  64. 			int mid = (r + l) / 2;
  65. 			if(right(x, rt, i, mid))r = mid;
  66. 			else l = mid;
  67. 		}
  68. 		rt[i] = r;
  69. 	}
  70. 	/*for(int i: lft)cout << i << " ";
  71. 	cout << endl;
  72. 	for(int i: rt)cout << i << " ";*/
  73. 	int l = 0, r = 1e9;
  74. 	while(r - l > 1){
  75.         double mid = int (r + l) / 2;
  76.         if(enough(x, lft, rt, mid))r = mid;
  77.         else l = mid;
  78. 	}
  79. 	cout<< fixed << setprecision(1);
  80. 	double ans = r;
  81. 	if(enough(x, lft, rt, r - 0.5))ans -= 0.5;
  82. 	cout << ans;
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0.01s 15376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.5
https://ideone.com/K9fZhZ
language:
C++14 (gcc 8.3)
created:
5 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!