Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<set>
- #include<algorithm>
- #include<deque>
- #include<map>
- #include<cmath>
- #include<iomanip>
- using namespace std;
- #define int long long
- vector<double> vec;
- vector<double> lft;
- vector<double> rght;
- int n;
- bool f(double r) {
- for (int i = 0; i < n; i++) {
- double d1 = vec[i] + r + r;
- auto it = upper_bound(vec.begin(), vec.end(), d1);
- it--;
- int t = it - vec.begin();
- if(lft[i] + 1 <= r && rght[t] + 1 <= r) {
- return 1;
- }
- d1 -= r * 4;
- it = lower_bound(vec.begin(), vec.end(), d1);
- t = it - vec.begin();
- if (rght[i] + 1 <= r && lft[t] + 1 <= r) {
- return 1;
- }
- }
- return 0;
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cin >> n;
- vec.resize(n);
- for (int i = 0; i < n; i++) {
- cin >> vec[i];
- }
- sort(vec.begin(), vec.end());
- lft.resize(n);
- rght.resize(n);
- for (int i = 1; i < n; i++) {
- lft[i] = max(lft[i - 1] + 1, abs(vec[i] - vec[i - 1]));
- }
- for (int i = n - 2; i >= 0; i--) {
- rght[i] = max(abs(vec[i] - vec[i + 1]), rght[i + 1] + 1);
- }
- double l = 0;
- double r = 1e9;
- for(int i = 0; i < 50; ++i) {
- double m = (l + r) / 2.0;
- if (f(m)) {
- r = m;
- }
- else {
- l = m;
- }
- }
- cout << fixed << setprecision(1) << r;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement