Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iomanip>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.     int n; cin >> n;
  11.     vector<int> ve(n);
  12.     for (int i = 0; i < n; ++i) cin >> ve[i];
  13.     sort(ve.begin(), ve.end());
  14.     ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
  15.     n = ve.size();
  16.     vector<pair<int,int> > ans(n, { -1, -1 });
  17.     ans[0].first = 0;
  18.     for (int i = 1; i < n; ++i) {
  19.         ans[i].first = max(ve[i] - ve[i - 1], ans[i - 1].first + 1);
  20.     }
  21.     ans.back().second = 0;
  22.     for (int i = n - 2; i >= 0; --i) {
  23.         ans[i].second = max(ve[i + 1] - ve[i], ans[i + 1].second + 1);
  24.     }
  25.     double res = (ve.back() - ve.front()) / 2.0;
  26.     for (int i = 0; i < n; ++i) {
  27.         double l = ans[i].first + 1, r = 1e9 + 4;
  28.         for (int q = 0; q < 60; ++q) {
  29.             double m = (l + r) / 2;
  30.             int rp = upper_bound(ve.begin(), ve.end(), ve[i] + 2 * m) - ve.begin() - 1;
  31.             if (ans[rp].second + 1 <= m) {
  32.                 r = m;
  33.             }
  34.             else {
  35.                 l = m;
  36.             }
  37.         }
  38.         res = min(l, res);
  39.     }
  40.     cout << fixed << setprecision(1) << res;
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement