Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- int main()
- {
- int n; cin >> n;
- vector<int> ve(n);
- for (int i = 0; i < n; ++i) cin >> ve[i];
- sort(ve.begin(), ve.end());
- ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
- n = ve.size();
- vector<pair<int,int> > ans(n, { -1, -1 });
- ans[0].first = 0;
- for (int i = 1; i < n; ++i) {
- ans[i].first = max(ve[i] - ve[i - 1], ans[i - 1].first + 1);
- }
- ans.back().second = 0;
- for (int i = n - 2; i >= 0; --i) {
- ans[i].second = max(ve[i + 1] - ve[i], ans[i + 1].second + 1);
- }
- double res = (ve.back() - ve.front()) / 2.0;
- for (int i = 0; i < n; ++i) {
- double l = ans[i].first + 1, r = 1e9 + 4;
- for (int q = 0; q < 60; ++q) {
- double m = (l + r) / 2;
- int rp = upper_bound(ve.begin(), ve.end(), ve[i] + 2 * m) - ve.begin() - 1;
- if (ans[rp].second + 1 <= m) {
- r = m;
- }
- else {
- l = m;
- }
- }
- res = min(l, res);
- }
- cout << fixed << setprecision(1) << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement