Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<set>
  4. #include<algorithm>
  5. #include<deque>
  6. #include<map>
  7. #include<cmath>
  8. #include<iomanip>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13.  
  14. vector<double> vec;
  15. vector<double> lft;
  16. vector<double> rght;
  17. int n;
  18.  
  19. bool f(double r) {
  20. for (int i = 0; i < n; i++) {
  21. double d1 = vec[i] + r + r;
  22. auto it = upper_bound(vec.begin(), vec.end(), d1);
  23. it--;
  24. int t = it - vec.begin();
  25. if(lft[i] + 1 <= r && rght[t] + 1 <= r) {
  26. return 1;
  27. }
  28. d1 -= r * 4;
  29. it = lower_bound(vec.begin(), vec.end(), d1);
  30. t = it - vec.begin();
  31. if (rght[i] + 1 <= r && lft[t] + 1 <= r) {
  32. return 1;
  33. }
  34. }
  35. return 0;
  36. }
  37.  
  38. signed main()
  39. {
  40. ios_base::sync_with_stdio(false);
  41. cin.tie(0);
  42. cin >> n;
  43. vec.resize(n);
  44. for (int i = 0; i < n; i++) {
  45. cin >> vec[i];
  46. }
  47. sort(vec.begin(), vec.end());
  48. lft.resize(n);
  49. rght.resize(n);
  50. for (int i = 1; i < n; i++) {
  51. lft[i] = max(lft[i - 1] + 1, abs(vec[i] - vec[i - 1]));
  52. }
  53. for (int i = n - 2; i >= 0; i--) {
  54. rght[i] = max(abs(vec[i] - vec[i + 1]), rght[i + 1] + 1);
  55. }
  56. double l = 0;
  57. double r = 1e9;
  58. for(int i = 0; i < 50; ++i) {
  59. double m = (l + r) / 2.0;
  60. if (f(m)) {
  61. r = m;
  62. }
  63. else {
  64. l = m;
  65. }
  66. }
  67. cout << fixed << setprecision(1) << r;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement