fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4. int L[51515], R[51515],a[51515], n;
  5. int max(int a, int b) { if (a < b)return b; return a; }
  6. bool f(int x) {
  7. 	int s, e = 0;
  8. 	for (s = 0; s < n; s++) {
  9. 		while (e + 1 < n&&a[e + 1] <= a[s] + 2 * x)e++;
  10. 		if (max(L[s], R[e]) <= x - 2)return 1;
  11. 	}
  12. 	return 0;
  13. }
  14. int main() {
  15. 	int i, j, p;
  16. 	scanf("%d", &n);
  17. 	for (i = 0; i < n; i++) scanf("%d", &a[i]), a[i] *= 2;
  18. 	sort(a, a + n);
  19. 	for (i = 1, p = 0; i < n; i++) {
  20. 		while (p + 1 < i&&max(L[p] + 2, a[i] - a[p]) > max(L[p + 1] + 2, a[i] - a[p + 1]))p++;
  21. 		L[i] = max(L[p] + 2, a[i] - a[p]);
  22. 	}
  23. 	for (i = n - 2, p = n - 1; i >= 0; i--) {
  24. 		while (p - 1 > i&&max(R[p] + 2, a[p] - a[i]) > max(R[p - 1] + 2, a[p - 1] - a[i]))p--;
  25. 		R[i] = max(R[p] + 2, a[p] - a[i]);
  26. 	}
  27. 	int s = 0, e = 1e9, ans;
  28. 	while (s <= e) {
  29. 		int m = (s + e) / 2;
  30. 		if (f(m))ans = m, e = m - 1;
  31. 		else s = m + 1;
  32. 	}
  33. 	printf("%d.%d", ans / 2, ans % 2 * 5);
  34. 	return 0;
  35. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
5
8
10
3
11
1
stdout
copy 
3.0
https://ideone.com/p7VxyO
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!