Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Bismillahir Rahmanir Rahim
- Farsid
- BUET
- */
- #include <bits/stdc++.h>
- using namespace std;
- #define SET(a, x) memset((a), (x), sizeof(a))
- #define ll long long
- #define pb push_back
- #define mp make_pair
- #define all(x) (x).begin(),(x).end()
- #define SZ(x) ((int)(x).size())
- #define i64 ll
- #define IN(A, B, C) ((B) <= (A) && (A) <= (C))
- #define MAX
- #define xx first
- #define yy second
- typedef vector<int> VI;
- typedef vector<string> VS;
- typedef vector<double> VD;
- typedef vector<ll> VL;
- typedef pair<int,int> PII;
- typedef pair<ll,ll> PLL;
- const int inf=0x20202020;
- const ll linf=(((i64)1)<<60)-1;
- const ll mod=1000000007;
- const double eps=1e-9;
- const double pi=3.1415926535897932384626;
- const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};
- ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
- ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
- ll inv_mod(ll a,ll mod){return powmod(a,mod-2,mod);}
- void print(double n)
- {
- printf("%.9lf\n",n);
- //cout<<n<<endl;
- }
- double A[200009];
- int n;
- double f(double x)
- {
- double ans=0,pos=0,neg=0;
- for(int i=0;i<n;i++){
- double a=A[i]-x;
- ans=max(ans,abs(a));
- pos+=a;
- if(pos<0)pos=0;
- neg+=a;
- if(neg>0)neg=0;
- ans=max(ans,pos);
- ans=max(ans,abs(neg));
- }
- return ans;
- }
- double t_search(double lo, double hi)
- {
- double md1,md2,ans;
- for(int i=0;i<300;i++){
- md1=lo+(hi-lo)/3.0;
- md2=lo+(2*(hi-lo))/3.0;
- double a1=f(md1),a2=f(md2);
- if(a2<a1){
- lo=md1;
- ans=a2;
- }
- else{
- hi=md2;
- ans=a1;
- }
- }
- return ans;
- }
- int main()
- {
- //freopen("far.in","r",stdin);
- //freopen("gadha.out","w",stdout);
- int i,j,k ,T,cas=0;
- //scanf("%d",&T);
- cin>>n;
- double mn=inf,mx=-inf;
- for(i=0;i<n;i++){
- cin>>A[i];
- mn=min(mn,A[i]);
- mx=max(mx,A[i]);
- }
- double ans=t_search(mn-10,mx+10);
- print(ans);
- return 0;
- }
- /*Test Cases
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement